<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN"
    "http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd">
<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en" lang="en">
<head>
<title>bn.tex</title>
<style type="text/css">
.enscript-comment { font-style: italic; color: rgb(178,34,34); }
.enscript-function-name { font-weight: bold; color: rgb(0,0,255); }
.enscript-variable-name { font-weight: bold; color: rgb(184,134,11); }
.enscript-keyword { font-weight: bold; color: rgb(160,32,240); }
.enscript-reference { font-weight: bold; color: rgb(95,158,160); }
.enscript-string { font-weight: bold; color: rgb(188,143,143); }
.enscript-builtin { font-weight: bold; color: rgb(218,112,214); }
.enscript-type { font-weight: bold; color: rgb(34,139,34); }
.enscript-highlight { text-decoration: underline; color: 0; }
</style>
</head>
<body id="top">
<h1 style="margin:8px;" id="f1">bn.tex&nbsp;&nbsp;&nbsp;<span style="font-weight: normal; font-size: 0.5em;">[<a href="bn.tex">plain text</a>]</span></h1>
<hr/>
<div></div>
<pre>
<span class="enscript-keyword">\documentclass</span>[synpaper]{book}
<span class="enscript-keyword">\usepackage</span>{hyperref}
<span class="enscript-keyword">\usepackage</span>{makeidx}
<span class="enscript-keyword">\usepackage</span>{amssymb}
<span class="enscript-keyword">\usepackage</span>{color}
<span class="enscript-keyword">\usepackage</span>{alltt}
<span class="enscript-keyword">\usepackage</span>{graphicx}
<span class="enscript-keyword">\usepackage</span>{layout}
<span class="enscript-keyword">\def</span><span class="enscript-keyword">\union</span>{<span class="enscript-keyword">\cup</span>}
<span class="enscript-keyword">\def</span><span class="enscript-keyword">\intersect</span>{<span class="enscript-keyword">\cap</span>}
<span class="enscript-keyword">\def</span><span class="enscript-keyword">\getsrandom</span>{<span class="enscript-keyword">\stackrel</span>{<span class="enscript-keyword">\rm</span> R}{<span class="enscript-keyword">\gets</span>}}
<span class="enscript-keyword">\def</span><span class="enscript-keyword">\cross</span>{<span class="enscript-keyword">\times</span>}
<span class="enscript-keyword">\def</span><span class="enscript-keyword">\cat</span>{<span class="enscript-keyword">\hspace</span>{0.5em} <span class="enscript-keyword">\|</span> <span class="enscript-keyword">\hspace</span>{0.5em}}
<span class="enscript-keyword">\def</span><span class="enscript-keyword">\catn</span>{<span class="enscript-variable-name">$\|$</span>}
<span class="enscript-keyword">\def</span><span class="enscript-keyword">\divides</span>{<span class="enscript-keyword">\hspace</span>{0.3em} | <span class="enscript-keyword">\hspace</span>{0.3em}}
<span class="enscript-keyword">\def</span><span class="enscript-keyword">\nequiv</span>{<span class="enscript-keyword">\not</span><span class="enscript-keyword">\equiv</span>}
<span class="enscript-keyword">\def</span><span class="enscript-keyword">\approx</span>{<span class="enscript-keyword">\raisebox</span>{0.2ex}{<span class="enscript-keyword">\mbox</span>{<span class="enscript-keyword">\small</span> <span class="enscript-variable-name">$\sim$</span>}}}
<span class="enscript-keyword">\def</span><span class="enscript-keyword">\lcm</span>{{<span class="enscript-keyword">\rm</span> lcm}}
<span class="enscript-keyword">\def</span><span class="enscript-keyword">\gcd</span>{{<span class="enscript-keyword">\rm</span> gcd}}
<span class="enscript-keyword">\def</span><span class="enscript-keyword">\log</span>{{<span class="enscript-keyword">\rm</span> log}}
<span class="enscript-keyword">\def</span><span class="enscript-keyword">\ord</span>{{<span class="enscript-keyword">\rm</span> ord}}
<span class="enscript-keyword">\def</span><span class="enscript-keyword">\abs</span>{{<span class="enscript-keyword">\mathit</span> abs}}
<span class="enscript-keyword">\def</span><span class="enscript-keyword">\rep</span>{{<span class="enscript-keyword">\mathit</span> rep}}
<span class="enscript-keyword">\def</span><span class="enscript-keyword">\mod</span>{{<span class="enscript-keyword">\mathit</span><span class="enscript-keyword">\ </span>mod<span class="enscript-keyword">\ </span>}}
<span class="enscript-keyword">\renewcommand</span>{<span class="enscript-keyword">\pmod</span>}[1]{<span class="enscript-keyword">\ </span>({<span class="enscript-keyword">\rm</span> mod<span class="enscript-keyword">\ </span>}{#1})}
<span class="enscript-keyword">\newcommand</span>{<span class="enscript-keyword">\floor</span>}[1]{<span class="enscript-keyword">\left</span><span class="enscript-keyword">\lfloor</span>{#1}<span class="enscript-keyword">\right</span><span class="enscript-keyword">\rfloor</span>}
<span class="enscript-keyword">\newcommand</span>{<span class="enscript-keyword">\ceil</span>}[1]{<span class="enscript-keyword">\left</span><span class="enscript-keyword">\lceil</span>{#1}<span class="enscript-keyword">\right</span><span class="enscript-keyword">\rceil</span>}
<span class="enscript-keyword">\def</span><span class="enscript-keyword">\Or</span>{{<span class="enscript-keyword">\rm</span><span class="enscript-keyword">\ </span>or<span class="enscript-keyword">\ </span>}}
<span class="enscript-keyword">\def</span><span class="enscript-keyword">\And</span>{{<span class="enscript-keyword">\rm</span><span class="enscript-keyword">\ </span>and<span class="enscript-keyword">\ </span>}}
<span class="enscript-keyword">\def</span><span class="enscript-keyword">\iff</span>{<span class="enscript-keyword">\hspace</span>{1em}<span class="enscript-keyword">\Longleftrightarrow</span><span class="enscript-keyword">\hspace</span>{1em}}
<span class="enscript-keyword">\def</span><span class="enscript-keyword">\implies</span>{<span class="enscript-keyword">\Rightarrow</span>}
<span class="enscript-keyword">\def</span><span class="enscript-keyword">\undefined</span>{{<span class="enscript-keyword">\rm</span> ``undefined&quot;}}
<span class="enscript-keyword">\def</span><span class="enscript-keyword">\Proof</span>{<span class="enscript-keyword">\vspace</span>{1ex}<span class="enscript-keyword">\noindent</span> {<span class="enscript-keyword">\bf</span> Proof:}<span class="enscript-keyword">\hspace</span>{1em}}
<span class="enscript-keyword">\let</span><span class="enscript-keyword">\oldphi</span><span class="enscript-keyword">\phi</span>
<span class="enscript-keyword">\def</span><span class="enscript-keyword">\phi</span>{<span class="enscript-keyword">\varphi</span>}
<span class="enscript-keyword">\def</span><span class="enscript-keyword">\Pr</span>{{<span class="enscript-keyword">\rm</span> Pr}}
<span class="enscript-keyword">\newcommand</span>{<span class="enscript-keyword">\str</span>}[1]{{<span class="enscript-keyword">\mathbf</span>{#1}}}
<span class="enscript-keyword">\def</span><span class="enscript-keyword">\F</span>{{<span class="enscript-keyword">\mathbb</span> F}}
<span class="enscript-keyword">\def</span><span class="enscript-keyword">\N</span>{{<span class="enscript-keyword">\mathbb</span> N}}
<span class="enscript-keyword">\def</span><span class="enscript-keyword">\Z</span>{{<span class="enscript-keyword">\mathbb</span> Z}}
<span class="enscript-keyword">\def</span><span class="enscript-keyword">\R</span>{{<span class="enscript-keyword">\mathbb</span> R}}
<span class="enscript-keyword">\def</span><span class="enscript-keyword">\C</span>{{<span class="enscript-keyword">\mathbb</span> C}}
<span class="enscript-keyword">\def</span><span class="enscript-keyword">\Q</span>{{<span class="enscript-keyword">\mathbb</span> Q}}
<span class="enscript-keyword">\definecolor</span>{DGray}{gray}{0.5}
<span class="enscript-keyword">\newcommand</span>{<span class="enscript-keyword">\emailaddr</span>}[1]{<span class="enscript-keyword">\mbox</span>{<span class="enscript-variable-name">$&lt;$</span>{#1}<span class="enscript-variable-name">$&gt;$</span>}}
<span class="enscript-keyword">\def</span><span class="enscript-keyword">\twiddle</span>{<span class="enscript-keyword">\raisebox</span>{0.3ex}{<span class="enscript-keyword">\mbox</span>{<span class="enscript-keyword">\tiny</span> <span class="enscript-variable-name">$\sim$</span>}}}
<span class="enscript-keyword">\def</span><span class="enscript-keyword">\gap</span>{<span class="enscript-keyword">\vspace</span>{0.5ex}}
<span class="enscript-keyword">\makeindex</span>
<span class="enscript-keyword">\begin</span>{document}
<span class="enscript-keyword">\frontmatter</span>
<span class="enscript-keyword">\pagestyle</span>{empty}
<span class="enscript-keyword">\title</span>{LibTomMath User Manual <span class="enscript-keyword">\\</span> v0.41}
<span class="enscript-keyword">\author</span>{Tom St Denis <span class="enscript-keyword">\\</span> <a href="mailto:tomstdenis@gmail.com">tomstdenis@gmail.com</a>}
<span class="enscript-keyword">\maketitle</span>
This text, the library and the accompanying textbook are all hereby placed in the public domain.  This book has been 
formatted for B5 [176x250] paper using the <span class="enscript-keyword">\LaTeX</span>{} {<span class="enscript-keyword">\em</span> book} macro package.

<span class="enscript-keyword">\vspace</span>{10cm}

<span class="enscript-keyword">\begin</span>{flushright}Open Source.  Open Academia.  Open Minds.

<span class="enscript-keyword">\mbox</span>{ }

Tom St Denis,

Ontario, Canada
<span class="enscript-keyword">\end</span>{flushright}

<span class="enscript-keyword">\tableofcontents</span>
<span class="enscript-keyword">\listoffigures</span>
<span class="enscript-keyword">\mainmatter</span>
<span class="enscript-keyword">\pagestyle</span>{headings}
<span class="enscript-keyword">\chapter</span>{Introduction}
<span class="enscript-keyword">\section</span>{What is LibTomMath?}
LibTomMath is a library of source code which provides a series of efficient and carefully written functions for manipulating
large integer numbers.  It was written in portable ISO C source code so that it will build on any platform with a conforming
C compiler.  

In a nutshell the library was written from scratch with verbose comments to help instruct computer science students how
to implement ``bignum'' math.  However, the resulting code has proven to be very useful.  It has been used by numerous 
universities, commercial and open source software developers.  It has been used on a variety of platforms ranging from
Linux and Windows based x86 to ARM based Gameboys and PPC based MacOS machines.  

<span class="enscript-keyword">\section</span>{License}
As of the v0.25 the library source code has been placed in the public domain with every new release.  As of the v0.28
release the textbook ``Implementing Multiple Precision Arithmetic'' has been placed in the public domain with every new
release as well.  This textbook is meant to compliment the project by providing a more solid walkthrough of the development
algorithms used in the library.

Since both<span class="enscript-keyword">\footnote</span>{Note that the MPI files under mtest/ are copyrighted by Michael Fromberger.  They are not required to use LibTomMath.} are in the 
public domain everyone is entitled to do with them as they see fit.

<span class="enscript-keyword">\section</span>{Building LibTomMath}

LibTomMath is meant to be very ``GCC friendly'' as it comes with a makefile well suited for GCC.  However, the library will
also build in MSVC, Borland C out of the box.  For any other ISO C compiler a makefile will have to be made by the end
developer.  

<span class="enscript-keyword">\subsection</span>{Static Libraries}
To build as a static library for GCC issue the following
<span class="enscript-keyword">\begin</span>{alltt}
make
<span class="enscript-keyword">\end</span>{alltt}

command.  This will build the library and archive the object files in ``libtommath.a''.  Now you link against 
that and include ``tommath.h'' within your programs.  Alternatively to build with MSVC issue the following
<span class="enscript-keyword">\begin</span>{alltt}
nmake -f makefile.msvc
<span class="enscript-keyword">\end</span>{alltt}

This will build the library and archive the object files in ``tommath.lib''.  This has been tested with MSVC 
version 6.00 with service pack 5.  

<span class="enscript-keyword">\subsection</span>{Shared Libraries}
To build as a shared library for GCC issue the following
<span class="enscript-keyword">\begin</span>{alltt}
make -f makefile.shared
<span class="enscript-keyword">\end</span>{alltt}
This requires the ``libtool'' package (common on most Linux/BSD systems).  It will build LibTomMath as both shared
and static then install (by default) into /usr/lib as well as install the header files in /usr/include.  The shared 
library (resource) will be called ``libtommath.la'' while the static library called ``libtommath.a''.  Generally 
you use libtool to link your application against the shared object.  

There is limited support for making a ``DLL'' in windows via the ``makefile.cygwin<span class="enscript-keyword">\_</span>dll'' makefile.  It requires 
Cygwin to work with since it requires the auto-export/import functionality.  The resulting DLL and import library 
``libtommath.dll.a'' can be used to link LibTomMath dynamically to any Windows program using Cygwin.

<span class="enscript-keyword">\subsection</span>{Testing}
To build the library and the test harness type

<span class="enscript-keyword">\begin</span>{alltt}
make test
<span class="enscript-keyword">\end</span>{alltt}

This will build the library, ``test'' and ``mtest/mtest''.  The ``test'' program will accept test vectors and verify the
results.  ``mtest/mtest'' will generate test vectors using the MPI library by Michael Fromberger<span class="enscript-keyword">\footnote</span>{A copy of MPI
is included in the package}.  Simply pipe mtest into test using

<span class="enscript-keyword">\begin</span>{alltt}
mtest/mtest | test
<span class="enscript-keyword">\end</span>{alltt}

If you do not have a ``/dev/urandom'' style RNG source you will have to write your own PRNG and simply pipe that into 
mtest.  For example, if your PRNG program is called ``myprng'' simply invoke

<span class="enscript-keyword">\begin</span>{alltt}
myprng | mtest/mtest | test
<span class="enscript-keyword">\end</span>{alltt}

This will output a row of numbers that are increasing.  Each column is a different test (such as addition, multiplication, etc)
that is being performed.  The numbers represent how many times the test was invoked.  If an error is detected the program
will exit with a dump of the relevent numbers it was working with.

<span class="enscript-keyword">\section</span>{Build Configuration}
LibTomMath can configured at build time in three phases we shall call ``depends'', ``tweaks'' and ``trims''.  
Each phase changes how the library is built and they are applied one after another respectively.  

To make the system more powerful you can tweak the build process.  Classes are defined in the file
``tommath<span class="enscript-keyword">\_</span>superclass.h''.  By default, the symbol ``LTM<span class="enscript-keyword">\_</span>ALL'' shall be defined which simply 
instructs the system to build all of the functions.  This is how LibTomMath used to be packaged.  This will give you 
access to every function LibTomMath offers.

However, there are cases where such a build is not optional.  For instance, you want to perform RSA operations.  You 
don't need the vast majority of the library to perform these operations.  Aside from LTM<span class="enscript-keyword">\_</span>ALL there is 
another pre--defined class ``SC<span class="enscript-keyword">\_</span>RSA<span class="enscript-keyword">\_</span>1'' which works in conjunction with the RSA from LibTomCrypt.  Additional 
classes can be defined base on the need of the user.

<span class="enscript-keyword">\subsection</span>{Build Depends}
In the file tommath<span class="enscript-keyword">\_</span>class.h you will see a large list of C ``defines'' followed by a series of ``ifdefs''
which further define symbols.  All of the symbols (technically they're macros <span class="enscript-variable-name">$\ldots$</span>) represent a given C source
file.  For instance, BN<span class="enscript-keyword">\_</span>MP<span class="enscript-keyword">\_</span>ADD<span class="enscript-keyword">\_</span>C represents the file ``bn<span class="enscript-keyword">\_</span>mp<span class="enscript-keyword">\_</span>add.c''.  When a define has been enabled the
function in the respective file will be compiled and linked into the library.  Accordingly when the define
is absent the file will not be compiled and not contribute any size to the library.

You will also note that the header tommath<span class="enscript-keyword">\_</span>class.h is actually recursively included (it includes itself twice).  
This is to help resolve as many dependencies as possible.  In the last pass the symbol LTM<span class="enscript-keyword">\_</span>LAST will be defined.  
This is useful for ``trims''.

<span class="enscript-keyword">\subsection</span>{Build Tweaks}
A tweak is an algorithm ``alternative''.  For example, to provide tradeoffs (usually between size and space).
They can be enabled at any pass of the configuration phase.

<span class="enscript-keyword">\begin</span>{small}
<span class="enscript-keyword">\begin</span>{center}
<span class="enscript-keyword">\begin</span>{tabular}{|l|l|}
<span class="enscript-keyword">\hline</span> <span class="enscript-keyword">\textbf</span>{Define} &amp; <span class="enscript-keyword">\textbf</span>{Purpose} <span class="enscript-keyword">\\</span>
<span class="enscript-keyword">\hline</span> BN<span class="enscript-keyword">\_</span>MP<span class="enscript-keyword">\_</span>DIV<span class="enscript-keyword">\_</span>SMALL &amp; Enables a slower, smaller and equally <span class="enscript-keyword">\\</span>
                          &amp; functional mp<span class="enscript-keyword">\_</span>div() function <span class="enscript-keyword">\\</span>
<span class="enscript-keyword">\hline</span>
<span class="enscript-keyword">\end</span>{tabular}
<span class="enscript-keyword">\end</span>{center}
<span class="enscript-keyword">\end</span>{small}

<span class="enscript-keyword">\subsection</span>{Build Trims}
A trim is a manner of removing functionality from a function that is not required.  For instance, to perform
RSA cryptography you only require exponentiation with odd moduli so even moduli support can be safely removed.  
Build trims are meant to be defined on the last pass of the configuration which means they are to be defined
only if LTM<span class="enscript-keyword">\_</span>LAST has been defined.

<span class="enscript-keyword">\subsubsection</span>{Moduli Related}
<span class="enscript-keyword">\begin</span>{small}
<span class="enscript-keyword">\begin</span>{center}
<span class="enscript-keyword">\begin</span>{tabular}{|l|l|}
<span class="enscript-keyword">\hline</span> <span class="enscript-keyword">\textbf</span>{Restriction} &amp; <span class="enscript-keyword">\textbf</span>{Undefine} <span class="enscript-keyword">\\</span>
<span class="enscript-keyword">\hline</span> Exponentiation with odd moduli only &amp; BN<span class="enscript-keyword">\_</span>S<span class="enscript-keyword">\_</span>MP<span class="enscript-keyword">\_</span>EXPTMOD<span class="enscript-keyword">\_</span>C <span class="enscript-keyword">\\</span>
                                           &amp; BN<span class="enscript-keyword">\_</span>MP<span class="enscript-keyword">\_</span>REDUCE<span class="enscript-keyword">\_</span>C <span class="enscript-keyword">\\</span>
                                           &amp; BN<span class="enscript-keyword">\_</span>MP<span class="enscript-keyword">\_</span>REDUCE<span class="enscript-keyword">\_</span>SETUP<span class="enscript-keyword">\_</span>C <span class="enscript-keyword">\\</span>
                                           &amp; BN<span class="enscript-keyword">\_</span>S<span class="enscript-keyword">\_</span>MP<span class="enscript-keyword">\_</span>MUL<span class="enscript-keyword">\_</span>HIGH<span class="enscript-keyword">\_</span>DIGS<span class="enscript-keyword">\_</span>C <span class="enscript-keyword">\\</span>
                                           &amp; BN<span class="enscript-keyword">\_</span>FAST<span class="enscript-keyword">\_</span>S<span class="enscript-keyword">\_</span>MP<span class="enscript-keyword">\_</span>MUL<span class="enscript-keyword">\_</span>HIGH<span class="enscript-keyword">\_</span>DIGS<span class="enscript-keyword">\_</span>C <span class="enscript-keyword">\\</span>
<span class="enscript-keyword">\hline</span> Exponentiation with random odd moduli &amp; (The above plus the following) <span class="enscript-keyword">\\</span>
                                           &amp; BN<span class="enscript-keyword">\_</span>MP<span class="enscript-keyword">\_</span>REDUCE<span class="enscript-keyword">\_</span>2K<span class="enscript-keyword">\_</span>C <span class="enscript-keyword">\\</span>
                                           &amp; BN<span class="enscript-keyword">\_</span>MP<span class="enscript-keyword">\_</span>REDUCE<span class="enscript-keyword">\_</span>2K<span class="enscript-keyword">\_</span>SETUP<span class="enscript-keyword">\_</span>C <span class="enscript-keyword">\\</span>
                                           &amp; BN<span class="enscript-keyword">\_</span>MP<span class="enscript-keyword">\_</span>REDUCE<span class="enscript-keyword">\_</span>IS<span class="enscript-keyword">\_</span>2K<span class="enscript-keyword">\_</span>C <span class="enscript-keyword">\\</span>
                                           &amp; BN<span class="enscript-keyword">\_</span>MP<span class="enscript-keyword">\_</span>DR<span class="enscript-keyword">\_</span>IS<span class="enscript-keyword">\_</span>MODULUS<span class="enscript-keyword">\_</span>C <span class="enscript-keyword">\\</span>
                                           &amp; BN<span class="enscript-keyword">\_</span>MP<span class="enscript-keyword">\_</span>DR<span class="enscript-keyword">\_</span>REDUCE<span class="enscript-keyword">\_</span>C <span class="enscript-keyword">\\</span>
                                           &amp; BN<span class="enscript-keyword">\_</span>MP<span class="enscript-keyword">\_</span>DR<span class="enscript-keyword">\_</span>SETUP<span class="enscript-keyword">\_</span>C <span class="enscript-keyword">\\</span>
<span class="enscript-keyword">\hline</span> Modular inverse odd moduli only     &amp; BN<span class="enscript-keyword">\_</span>MP<span class="enscript-keyword">\_</span>INVMOD<span class="enscript-keyword">\_</span>SLOW<span class="enscript-keyword">\_</span>C <span class="enscript-keyword">\\</span>
<span class="enscript-keyword">\hline</span> Modular inverse (both, smaller/slower) &amp; BN<span class="enscript-keyword">\_</span>FAST<span class="enscript-keyword">\_</span>MP<span class="enscript-keyword">\_</span>INVMOD<span class="enscript-keyword">\_</span>C <span class="enscript-keyword">\\</span>
<span class="enscript-keyword">\hline</span>
<span class="enscript-keyword">\end</span>{tabular}
<span class="enscript-keyword">\end</span>{center}
<span class="enscript-keyword">\end</span>{small}

<span class="enscript-keyword">\subsubsection</span>{Operand Size Related}
<span class="enscript-keyword">\begin</span>{small}
<span class="enscript-keyword">\begin</span>{center}
<span class="enscript-keyword">\begin</span>{tabular}{|l|l|}
<span class="enscript-keyword">\hline</span> <span class="enscript-keyword">\textbf</span>{Restriction} &amp; <span class="enscript-keyword">\textbf</span>{Undefine} <span class="enscript-keyword">\\</span>
<span class="enscript-keyword">\hline</span> Moduli <span class="enscript-variable-name">$\le 2560$</span> bits              &amp; BN<span class="enscript-keyword">\_</span>MP<span class="enscript-keyword">\_</span>MONTGOMERY<span class="enscript-keyword">\_</span>REDUCE<span class="enscript-keyword">\_</span>C <span class="enscript-keyword">\\</span>
                                           &amp; BN<span class="enscript-keyword">\_</span>S<span class="enscript-keyword">\_</span>MP<span class="enscript-keyword">\_</span>MUL<span class="enscript-keyword">\_</span>DIGS<span class="enscript-keyword">\_</span>C <span class="enscript-keyword">\\</span>
                                           &amp; BN<span class="enscript-keyword">\_</span>S<span class="enscript-keyword">\_</span>MP<span class="enscript-keyword">\_</span>MUL<span class="enscript-keyword">\_</span>HIGH<span class="enscript-keyword">\_</span>DIGS<span class="enscript-keyword">\_</span>C <span class="enscript-keyword">\\</span>
                                           &amp; BN<span class="enscript-keyword">\_</span>S<span class="enscript-keyword">\_</span>MP<span class="enscript-keyword">\_</span>SQR<span class="enscript-keyword">\_</span>C <span class="enscript-keyword">\\</span>
<span class="enscript-keyword">\hline</span> Polynomial Schmolynomial            &amp; BN<span class="enscript-keyword">\_</span>MP<span class="enscript-keyword">\_</span>KARATSUBA<span class="enscript-keyword">\_</span>MUL<span class="enscript-keyword">\_</span>C <span class="enscript-keyword">\\</span>
                                           &amp; BN<span class="enscript-keyword">\_</span>MP<span class="enscript-keyword">\_</span>KARATSUBA<span class="enscript-keyword">\_</span>SQR<span class="enscript-keyword">\_</span>C <span class="enscript-keyword">\\</span>
                                           &amp; BN<span class="enscript-keyword">\_</span>MP<span class="enscript-keyword">\_</span>TOOM<span class="enscript-keyword">\_</span>MUL<span class="enscript-keyword">\_</span>C <span class="enscript-keyword">\\</span> 
                                           &amp; BN<span class="enscript-keyword">\_</span>MP<span class="enscript-keyword">\_</span>TOOM<span class="enscript-keyword">\_</span>SQR<span class="enscript-keyword">\_</span>C <span class="enscript-keyword">\\</span>

<span class="enscript-keyword">\hline</span>
<span class="enscript-keyword">\end</span>{tabular}
<span class="enscript-keyword">\end</span>{center}
<span class="enscript-keyword">\end</span>{small}


<span class="enscript-keyword">\section</span>{Purpose of LibTomMath}
Unlike  GNU MP (GMP) Library, LIP, OpenSSL or various other commercial kits (Miracl), LibTomMath was not written with 
bleeding edge performance in mind.  First and foremost LibTomMath was written to be entirely open.  Not only is the 
source code public domain (unlike various other GPL/etc licensed code), not only is the code freely downloadable but the
source code is also accessible for computer science students attempting to learn ``BigNum'' or multiple precision
arithmetic techniques. 

LibTomMath was written to be an instructive collection of source code.  This is why there are many comments, only one
function per source file and often I use a ``middle-road'' approach where I don't cut corners for an extra 2\% speed
increase.

Source code alone cannot really teach how the algorithms work which is why I also wrote a textbook that accompanies
the library (beat that!).

So you may be thinking ``should I use LibTomMath?'' and the answer is a definite maybe.  Let me tabulate what I think
are the pros and cons of LibTomMath by comparing it to the math routines from GnuPG<span class="enscript-keyword">\footnote</span>{GnuPG v1.2.3 versus LibTomMath v0.28}.

<span class="enscript-keyword">\newpage</span><span class="enscript-keyword">\begin</span>{figure}[here]
<span class="enscript-keyword">\begin</span>{small}
<span class="enscript-keyword">\begin</span>{center}
<span class="enscript-keyword">\begin</span>{tabular}{|l|c|c|l|}
<span class="enscript-keyword">\hline</span> <span class="enscript-keyword">\textbf</span>{Criteria} &amp; <span class="enscript-keyword">\textbf</span>{Pro} &amp; <span class="enscript-keyword">\textbf</span>{Con} &amp; <span class="enscript-keyword">\textbf</span>{Notes} <span class="enscript-keyword">\\</span>
<span class="enscript-keyword">\hline</span> Few lines of code per file &amp; X &amp; &amp; GnuPG <span class="enscript-variable-name">$ = 300.9$</span>, LibTomMath  <span class="enscript-variable-name">$ = 71.97$</span> <span class="enscript-keyword">\\</span>
<span class="enscript-keyword">\hline</span> Commented function prototypes &amp; X &amp;&amp; GnuPG function names are cryptic. <span class="enscript-keyword">\\</span>
<span class="enscript-keyword">\hline</span> Speed &amp;&amp; X &amp; LibTomMath is slower.  <span class="enscript-keyword">\\</span>
<span class="enscript-keyword">\hline</span> Totally free &amp; X &amp; &amp; GPL has unfavourable restrictions.<span class="enscript-keyword">\\</span>
<span class="enscript-keyword">\hline</span> Large function base &amp; X &amp; &amp; GnuPG is barebones. <span class="enscript-keyword">\\</span>
<span class="enscript-keyword">\hline</span> Five modular reduction algorithms &amp; X &amp; &amp; Faster modular exponentiation for a variety of moduli. <span class="enscript-keyword">\\</span>
<span class="enscript-keyword">\hline</span> Portable &amp; X &amp; &amp; GnuPG requires configuration to build. <span class="enscript-keyword">\\</span>
<span class="enscript-keyword">\hline</span>
<span class="enscript-keyword">\end</span>{tabular}
<span class="enscript-keyword">\end</span>{center}
<span class="enscript-keyword">\end</span>{small}
<span class="enscript-keyword">\caption</span>{LibTomMath Valuation}
<span class="enscript-keyword">\end</span>{figure}

It may seem odd to compare LibTomMath to GnuPG since the math in GnuPG is only a small portion of the entire application. 
However, LibTomMath was written with cryptography in mind.  It provides essentially all of the functions a cryptosystem
would require when working with large integers.  

So it may feel tempting to just rip the math code out of GnuPG (or GnuMP where it was taken from originally) in your
own application but I think there are reasons not to.  While LibTomMath is slower than libraries such as GnuMP it is
not normally significantly slower.  On x86 machines the difference is normally a factor of two when performing modular
exponentiations.  It depends largely on the processor, compiler and the moduli being used.

Essentially the only time you wouldn't use LibTomMath is when blazing speed is the primary concern.  However,
on the other side of the coin LibTomMath offers you a totally free (public domain) well structured math library
that is very flexible, complete and performs well in resource contrained environments.  Fast RSA for example can
be performed with as little as 8KB of ram for data (again depending on build options).  

<span class="enscript-keyword">\chapter</span>{Getting Started with LibTomMath}
<span class="enscript-keyword">\section</span>{Building Programs}
In order to use LibTomMath you must include ``tommath.h'' and link against the appropriate library file (typically 
libtommath.a).  There is no library initialization required and the entire library is thread safe.

<span class="enscript-keyword">\section</span>{Return Codes}
There are three possible return codes a function may return.

<span class="enscript-keyword">\index</span>{MP<span class="enscript-keyword">\_</span>OKAY}<span class="enscript-keyword">\index</span>{MP<span class="enscript-keyword">\_</span>YES}<span class="enscript-keyword">\index</span>{MP<span class="enscript-keyword">\_</span>NO}<span class="enscript-keyword">\index</span>{MP<span class="enscript-keyword">\_</span>VAL}<span class="enscript-keyword">\index</span>{MP<span class="enscript-keyword">\_</span>MEM}
<span class="enscript-keyword">\begin</span>{figure}[here!]
<span class="enscript-keyword">\begin</span>{center}
<span class="enscript-keyword">\begin</span>{small}
<span class="enscript-keyword">\begin</span>{tabular}{|l|l|}
<span class="enscript-keyword">\hline</span> <span class="enscript-keyword">\textbf</span>{Code} &amp; <span class="enscript-keyword">\textbf</span>{Meaning} <span class="enscript-keyword">\\</span>
<span class="enscript-keyword">\hline</span> MP<span class="enscript-keyword">\_</span>OKAY &amp; The function succeeded. <span class="enscript-keyword">\\</span>
<span class="enscript-keyword">\hline</span> MP<span class="enscript-keyword">\_</span>VAL  &amp; The function input was invalid. <span class="enscript-keyword">\\</span>
<span class="enscript-keyword">\hline</span> MP<span class="enscript-keyword">\_</span>MEM  &amp; Heap memory exhausted. <span class="enscript-keyword">\\</span>
<span class="enscript-keyword">\hline</span> &amp;<span class="enscript-keyword">\\</span>
<span class="enscript-keyword">\hline</span> MP<span class="enscript-keyword">\_</span>YES  &amp; Response is yes. <span class="enscript-keyword">\\</span>
<span class="enscript-keyword">\hline</span> MP<span class="enscript-keyword">\_</span>NO   &amp; Response is no. <span class="enscript-keyword">\\</span>
<span class="enscript-keyword">\hline</span>
<span class="enscript-keyword">\end</span>{tabular}
<span class="enscript-keyword">\end</span>{small}
<span class="enscript-keyword">\end</span>{center}
<span class="enscript-keyword">\caption</span>{Return Codes}
<span class="enscript-keyword">\end</span>{figure}

The last two codes listed are not actually ``return'ed'' by a function.  They are placed in an integer (the caller must
provide the address of an integer it can store to) which the caller can access.  To convert one of the three return codes
to a string use the following function.

<span class="enscript-keyword">\index</span>{mp<span class="enscript-keyword">\_</span>error<span class="enscript-keyword">\_</span>to<span class="enscript-keyword">\_</span>string}
<span class="enscript-keyword">\begin</span>{alltt}
char *mp_error_to_string(int code);
<span class="enscript-keyword">\end</span>{alltt}

This will return a pointer to a string which describes the given error code.  It will not work for the return codes 
MP<span class="enscript-keyword">\_</span>YES and MP<span class="enscript-keyword">\_</span>NO.  

<span class="enscript-keyword">\section</span>{Data Types}
The basic ``multiple precision integer'' type is known as the ``mp<span class="enscript-keyword">\_</span>int'' within LibTomMath.  This data type is used to
organize all of the data required to manipulate the integer it represents.  Within LibTomMath it has been prototyped
as the following.

<span class="enscript-keyword">\index</span>{mp<span class="enscript-keyword">\_</span>int}
<span class="enscript-keyword">\begin</span>{alltt}
typedef struct  <span class="enscript-keyword">\{</span>
    int used, alloc, sign;
    mp_digit *dp;
<span class="enscript-keyword">\}</span> mp_int;
<span class="enscript-keyword">\end</span>{alltt}

Where ``mp<span class="enscript-keyword">\_</span>digit'' is a data type that represents individual digits of the integer.  By default, an mp<span class="enscript-keyword">\_</span>digit is the
ISO C ``unsigned long'' data type and each digit is <span class="enscript-variable-name">$28-$</span>bits long.  The mp<span class="enscript-keyword">\_</span>digit type can be configured to suit other
platforms by defining the appropriate macros.  

All LTM functions that use the mp<span class="enscript-keyword">\_</span>int type will expect a pointer to mp<span class="enscript-keyword">\_</span>int structure.  You must allocate memory to
hold the structure itself by yourself (whether off stack or heap it doesn't matter).  The very first thing that must be
done to use an mp<span class="enscript-keyword">\_</span>int is that it must be initialized.

<span class="enscript-keyword">\section</span>{Function Organization}

The arithmetic functions of the library are all organized to have the same style prototype.  That is source operands
are passed on the left and the destination is on the right.  For instance,

<span class="enscript-keyword">\begin</span>{alltt}
mp_add(&amp;a, &amp;b, &amp;c);       /* c = a + b */
mp_mul(&amp;a, &amp;a, &amp;c);       /* c = a * a */
mp_div(&amp;a, &amp;b, &amp;c, &amp;d);   /* c = [a/b], d = a mod b */
<span class="enscript-keyword">\end</span>{alltt}

Another feature of the way the functions have been implemented is that source operands can be destination operands as well.
For instance,

<span class="enscript-keyword">\begin</span>{alltt}
mp_add(&amp;a, &amp;b, &amp;b);       /* b = a + b */
mp_div(&amp;a, &amp;b, &amp;a, &amp;c);   /* a = [a/b], c = a mod b */
<span class="enscript-keyword">\end</span>{alltt}

This allows operands to be re-used which can make programming simpler.

<span class="enscript-keyword">\section</span>{Initialization}
<span class="enscript-keyword">\subsection</span>{Single Initialization}
A single mp<span class="enscript-keyword">\_</span>int can be initialized with the ``mp<span class="enscript-keyword">\_</span>init'' function. 

<span class="enscript-keyword">\index</span>{mp<span class="enscript-keyword">\_</span>init}
<span class="enscript-keyword">\begin</span>{alltt}
int mp_init (mp_int * a);
<span class="enscript-keyword">\end</span>{alltt}

This function expects a pointer to an mp<span class="enscript-keyword">\_</span>int structure and will initialize the members of the structure so the mp<span class="enscript-keyword">\_</span>int
represents the default integer which is zero.  If the functions returns MP<span class="enscript-keyword">\_</span>OKAY then the mp<span class="enscript-keyword">\_</span>int is ready to be used
by the other LibTomMath functions.

<span class="enscript-keyword">\begin</span>{small} <span class="enscript-keyword">\begin</span>{alltt}
int main(void)
<span class="enscript-keyword">\{</span>
   mp_int number;
   int result;

   if ((result = mp_init(&amp;number)) != MP_OKAY) <span class="enscript-keyword">\{</span>
      printf(&quot;Error initializing the number.  \%s&quot;, 
             mp_error_to_string(result));
      return EXIT_FAILURE;
   <span class="enscript-keyword">\}</span>
 
   /* use the number */

   return EXIT_SUCCESS;
<span class="enscript-keyword">\}</span>
<span class="enscript-keyword">\end</span>{alltt} <span class="enscript-keyword">\end</span>{small}

<span class="enscript-keyword">\subsection</span>{Single Free}
When you are finished with an mp<span class="enscript-keyword">\_</span>int it is ideal to return the heap it used back to the system.  The following function 
provides this functionality.

<span class="enscript-keyword">\index</span>{mp<span class="enscript-keyword">\_</span>clear}
<span class="enscript-keyword">\begin</span>{alltt}
void mp_clear (mp_int * a);
<span class="enscript-keyword">\end</span>{alltt}

The function expects a pointer to a previously initialized mp<span class="enscript-keyword">\_</span>int structure and frees the heap it uses.  It sets the 
pointer<span class="enscript-keyword">\footnote</span>{The ``dp'' member.} within the mp<span class="enscript-keyword">\_</span>int to <span class="enscript-keyword">\textbf</span>{NULL} which is used to prevent double free situations. 
Is is legal to call mp<span class="enscript-keyword">\_</span>clear() twice on the same mp<span class="enscript-keyword">\_</span>int in a row.  

<span class="enscript-keyword">\begin</span>{small} <span class="enscript-keyword">\begin</span>{alltt}
int main(void)
<span class="enscript-keyword">\{</span>
   mp_int number;
   int result;

   if ((result = mp_init(&amp;number)) != MP_OKAY) <span class="enscript-keyword">\{</span>
      printf(&quot;Error initializing the number.  \%s&quot;, 
             mp_error_to_string(result));
      return EXIT_FAILURE;
   <span class="enscript-keyword">\}</span>
 
   /* use the number */

   /* We're done with it. */
   mp_clear(&amp;number);

   return EXIT_SUCCESS;
<span class="enscript-keyword">\}</span>
<span class="enscript-keyword">\end</span>{alltt} <span class="enscript-keyword">\end</span>{small}

<span class="enscript-keyword">\subsection</span>{Multiple Initializations}
Certain algorithms require more than one large integer.  In these instances it is ideal to initialize all of the mp<span class="enscript-keyword">\_</span>int
variables in an ``all or nothing'' fashion.  That is, they are either all initialized successfully or they are all
not initialized.

The  mp<span class="enscript-keyword">\_</span>init<span class="enscript-keyword">\_</span>multi() function provides this functionality.

<span class="enscript-keyword">\index</span>{mp<span class="enscript-keyword">\_</span>init<span class="enscript-keyword">\_</span>multi} <span class="enscript-keyword">\index</span>{mp<span class="enscript-keyword">\_</span>clear<span class="enscript-keyword">\_</span>multi}
<span class="enscript-keyword">\begin</span>{alltt}
int mp_init_multi(mp_int *mp, ...);
<span class="enscript-keyword">\end</span>{alltt}

It accepts a <span class="enscript-keyword">\textbf</span>{NULL} terminated list of pointers to mp<span class="enscript-keyword">\_</span>int structures.  It will attempt to initialize them all
at once.  If the function returns MP<span class="enscript-keyword">\_</span>OKAY then all of the mp<span class="enscript-keyword">\_</span>int variables are ready to use, otherwise none of them
are available for use.  A complementary mp<span class="enscript-keyword">\_</span>clear<span class="enscript-keyword">\_</span>multi() function allows multiple mp<span class="enscript-keyword">\_</span>int variables to be free'd 
from the heap at the same time.  

<span class="enscript-keyword">\begin</span>{small} <span class="enscript-keyword">\begin</span>{alltt}
int main(void)
<span class="enscript-keyword">\{</span>
   mp_int num1, num2, num3;
   int result;

   if ((result = mp_init_multi(&amp;num1, 
                               &amp;num2,
                               &amp;num3, NULL)) != MP<span class="enscript-keyword">\_</span>OKAY) <span class="enscript-keyword">\{</span>      
      printf(&quot;Error initializing the numbers.  \%s&quot;, 
             mp_error_to_string(result));
      return EXIT_FAILURE;
   <span class="enscript-keyword">\}</span>
 
   /* use the numbers */

   /* We're done with them. */
   mp_clear_multi(&amp;num1, &amp;num2, &amp;num3, NULL);

   return EXIT_SUCCESS;
<span class="enscript-keyword">\}</span>
<span class="enscript-keyword">\end</span>{alltt} <span class="enscript-keyword">\end</span>{small}

<span class="enscript-keyword">\subsection</span>{Other Initializers}
To initialized and make a copy of an mp<span class="enscript-keyword">\_</span>int the mp<span class="enscript-keyword">\_</span>init<span class="enscript-keyword">\_</span>copy() function has been provided.  

<span class="enscript-keyword">\index</span>{mp<span class="enscript-keyword">\_</span>init<span class="enscript-keyword">\_</span>copy}
<span class="enscript-keyword">\begin</span>{alltt}
int mp_init_copy (mp_int * a, mp_int * b);
<span class="enscript-keyword">\end</span>{alltt}

This function will initialize <span class="enscript-variable-name">$a$</span> and make it a copy of <span class="enscript-variable-name">$b$</span> if all goes well.

<span class="enscript-keyword">\begin</span>{small} <span class="enscript-keyword">\begin</span>{alltt}
int main(void)
<span class="enscript-keyword">\{</span>
   mp_int num1, num2;
   int result;

   /* initialize and do work on num1 ... */

   /* We want a copy of num1 in num2 now */
   if ((result = mp_init_copy(&amp;num2, &amp;num1)) != MP_OKAY) <span class="enscript-keyword">\{</span>
     printf(&quot;Error initializing the copy.  \%s&quot;, 
             mp_error_to_string(result));
      return EXIT_FAILURE;
   <span class="enscript-keyword">\}</span>
 
   /* now num2 is ready and contains a copy of num1 */

   /* We're done with them. */
   mp_clear_multi(&amp;num1, &amp;num2, NULL);

   return EXIT_SUCCESS;
<span class="enscript-keyword">\}</span>
<span class="enscript-keyword">\end</span>{alltt} <span class="enscript-keyword">\end</span>{small}

Another less common initializer is mp<span class="enscript-keyword">\_</span>init<span class="enscript-keyword">\_</span>size() which allows the user to initialize an mp<span class="enscript-keyword">\_</span>int with a given
default number of digits.  By default, all initializers allocate <span class="enscript-keyword">\textbf</span>{MP<span class="enscript-keyword">\_</span>PREC} digits.  This function lets
you override this behaviour.

<span class="enscript-keyword">\index</span>{mp<span class="enscript-keyword">\_</span>init<span class="enscript-keyword">\_</span>size}
<span class="enscript-keyword">\begin</span>{alltt}
int mp_init_size (mp_int * a, int size);
<span class="enscript-keyword">\end</span>{alltt}

The <span class="enscript-variable-name">$size$</span> parameter must be greater than zero.  If the function succeeds the mp<span class="enscript-keyword">\_</span>int <span class="enscript-variable-name">$a$</span> will be initialized
to have <span class="enscript-variable-name">$size$</span> digits (which are all initially zero).  

<span class="enscript-keyword">\begin</span>{small} <span class="enscript-keyword">\begin</span>{alltt}
int main(void)
<span class="enscript-keyword">\{</span>
   mp_int number;
   int result;

   /* we need a 60-digit number */
   if ((result = mp_init_size(&amp;number, 60)) != MP_OKAY) <span class="enscript-keyword">\{</span>
      printf(&quot;Error initializing the number.  \%s&quot;, 
             mp_error_to_string(result));
      return EXIT_FAILURE;
   <span class="enscript-keyword">\}</span>
 
   /* use the number */

   return EXIT_SUCCESS;
<span class="enscript-keyword">\}</span>
<span class="enscript-keyword">\end</span>{alltt} <span class="enscript-keyword">\end</span>{small}

<span class="enscript-keyword">\section</span>{Maintenance Functions}

<span class="enscript-keyword">\subsection</span>{Reducing Memory Usage}
When an mp<span class="enscript-keyword">\_</span>int is in a state where it won't be changed again<span class="enscript-keyword">\footnote</span>{A Diffie-Hellman modulus for instance.} excess
digits can be removed to return memory to the heap with the mp<span class="enscript-keyword">\_</span>shrink() function.

<span class="enscript-keyword">\index</span>{mp<span class="enscript-keyword">\_</span>shrink}
<span class="enscript-keyword">\begin</span>{alltt}
int mp_shrink (mp_int * a);
<span class="enscript-keyword">\end</span>{alltt}

This will remove excess digits of the mp<span class="enscript-keyword">\_</span>int <span class="enscript-variable-name">$a$</span>.  If the operation fails the mp<span class="enscript-keyword">\_</span>int should be intact without the
excess digits being removed.  Note that you can use a shrunk mp<span class="enscript-keyword">\_</span>int in further computations, however, such operations
will require heap operations which can be slow.  It is not ideal to shrink mp<span class="enscript-keyword">\_</span>int variables that you will further
modify in the system (unless you are seriously low on memory).  

<span class="enscript-keyword">\begin</span>{small} <span class="enscript-keyword">\begin</span>{alltt}
int main(void)
<span class="enscript-keyword">\{</span>
   mp_int number;
   int result;

   if ((result = mp_init(&amp;number)) != MP_OKAY) <span class="enscript-keyword">\{</span>
      printf(&quot;Error initializing the number.  \%s&quot;, 
             mp_error_to_string(result));
      return EXIT_FAILURE;
   <span class="enscript-keyword">\}</span>
 
   /* use the number [e.g. pre-computation]  */

   /* We're done with it for now. */
   if ((result = mp_shrink(&amp;number)) != MP_OKAY) <span class="enscript-keyword">\{</span>
      printf(&quot;Error shrinking the number.  \%s&quot;, 
             mp_error_to_string(result));
      return EXIT_FAILURE;
   <span class="enscript-keyword">\}</span>

   /* use it .... */


   /* we're done with it. */ 
   mp_clear(&amp;number);

   return EXIT_SUCCESS;
<span class="enscript-keyword">\}</span>
<span class="enscript-keyword">\end</span>{alltt} <span class="enscript-keyword">\end</span>{small}

<span class="enscript-keyword">\subsection</span>{Adding additional digits}

Within the mp<span class="enscript-keyword">\_</span>int structure are two parameters which control the limitations of the array of digits that represent
the integer the mp<span class="enscript-keyword">\_</span>int is meant to equal.   The <span class="enscript-keyword">\textit</span>{used} parameter dictates how many digits are significant, that is,
contribute to the value of the mp<span class="enscript-keyword">\_</span>int.  The <span class="enscript-keyword">\textit</span>{alloc} parameter dictates how many digits are currently available in
the array.  If you need to perform an operation that requires more digits you will have to mp<span class="enscript-keyword">\_</span>grow() the mp<span class="enscript-keyword">\_</span>int to
your desired size.  

<span class="enscript-keyword">\index</span>{mp<span class="enscript-keyword">\_</span>grow}
<span class="enscript-keyword">\begin</span>{alltt}
int mp_grow (mp_int * a, int size);
<span class="enscript-keyword">\end</span>{alltt}

This will grow the array of digits of <span class="enscript-variable-name">$a$</span> to <span class="enscript-variable-name">$size$</span>.  If the <span class="enscript-keyword">\textit</span>{alloc} parameter is already bigger than
<span class="enscript-variable-name">$size$</span> the function will not do anything.

<span class="enscript-keyword">\begin</span>{small} <span class="enscript-keyword">\begin</span>{alltt}
int main(void)
<span class="enscript-keyword">\{</span>
   mp_int number;
   int result;

   if ((result = mp_init(&amp;number)) != MP_OKAY) <span class="enscript-keyword">\{</span>
      printf(&quot;Error initializing the number.  \%s&quot;, 
             mp_error_to_string(result));
      return EXIT_FAILURE;
   <span class="enscript-keyword">\}</span>
 
   /* use the number */

   /* We need to add 20 digits to the number  */
   if ((result = mp_grow(&amp;number, number.alloc + 20)) != MP_OKAY) <span class="enscript-keyword">\{</span>
      printf(&quot;Error growing the number.  \%s&quot;, 
             mp_error_to_string(result));
      return EXIT_FAILURE;
   <span class="enscript-keyword">\}</span>


   /* use the number */

   /* we're done with it. */ 
   mp_clear(&amp;number);

   return EXIT_SUCCESS;
<span class="enscript-keyword">\}</span>
<span class="enscript-keyword">\end</span>{alltt} <span class="enscript-keyword">\end</span>{small}

<span class="enscript-keyword">\chapter</span>{Basic Operations}
<span class="enscript-keyword">\section</span>{Small Constants}
Setting mp<span class="enscript-keyword">\_</span>ints to small constants is a relatively common operation.  To accomodate these instances there are two
small constant assignment functions.  The first function is used to set a single digit constant while the second sets
an ISO C style ``unsigned long'' constant.  The reason for both functions is efficiency.  Setting a single digit is quick but the
domain of a digit can change (it's always at least <span class="enscript-variable-name">$0 \ldots 127$</span>).  

<span class="enscript-keyword">\subsection</span>{Single Digit}

Setting a single digit can be accomplished with the following function.

<span class="enscript-keyword">\index</span>{mp<span class="enscript-keyword">\_</span>set}
<span class="enscript-keyword">\begin</span>{alltt}
void mp_set (mp_int * a, mp_digit b);
<span class="enscript-keyword">\end</span>{alltt}

This will zero the contents of <span class="enscript-variable-name">$a$</span> and make it represent an integer equal to the value of <span class="enscript-variable-name">$b$</span>.  Note that this
function has a return type of <span class="enscript-keyword">\textbf</span>{void}.  It cannot cause an error so it is safe to assume the function
succeeded.

<span class="enscript-keyword">\begin</span>{small} <span class="enscript-keyword">\begin</span>{alltt}
int main(void)
<span class="enscript-keyword">\{</span>
   mp_int number;
   int result;

   if ((result = mp_init(&amp;number)) != MP_OKAY) <span class="enscript-keyword">\{</span>
      printf(&quot;Error initializing the number.  \%s&quot;, 
             mp_error_to_string(result));
      return EXIT_FAILURE;
   <span class="enscript-keyword">\}</span>
 
   /* set the number to 5 */
   mp_set(&amp;number, 5);

   /* we're done with it. */ 
   mp_clear(&amp;number);

   return EXIT_SUCCESS;
<span class="enscript-keyword">\}</span>
<span class="enscript-keyword">\end</span>{alltt} <span class="enscript-keyword">\end</span>{small}

<span class="enscript-keyword">\subsection</span>{Long Constants}

To set a constant that is the size of an ISO C ``unsigned long'' and larger than a single digit the following function 
can be used.

<span class="enscript-keyword">\index</span>{mp<span class="enscript-keyword">\_</span>set<span class="enscript-keyword">\_</span>int}
<span class="enscript-keyword">\begin</span>{alltt}
int mp_set_int (mp_int * a, unsigned long b);
<span class="enscript-keyword">\end</span>{alltt}

This will assign the value of the 32-bit variable <span class="enscript-variable-name">$b$</span> to the mp<span class="enscript-keyword">\_</span>int <span class="enscript-variable-name">$a$</span>.  Unlike mp<span class="enscript-keyword">\_</span>set() this function will always
accept a 32-bit input regardless of the size of a single digit.  However, since the value may span several digits 
this function can fail if it runs out of heap memory.

To get the ``unsigned long'' copy of an mp<span class="enscript-keyword">\_</span>int the following function can be used.

<span class="enscript-keyword">\index</span>{mp<span class="enscript-keyword">\_</span>get<span class="enscript-keyword">\_</span>int}
<span class="enscript-keyword">\begin</span>{alltt}
unsigned long mp_get_int (mp_int * a);
<span class="enscript-keyword">\end</span>{alltt}

This will return the 32 least significant bits of the mp<span class="enscript-keyword">\_</span>int <span class="enscript-variable-name">$a$</span>.  

<span class="enscript-keyword">\begin</span>{small} <span class="enscript-keyword">\begin</span>{alltt}
int main(void)
<span class="enscript-keyword">\{</span>
   mp_int number;
   int result;

   if ((result = mp_init(&amp;number)) != MP_OKAY) <span class="enscript-keyword">\{</span>
      printf(&quot;Error initializing the number.  \%s&quot;, 
             mp_error_to_string(result));
      return EXIT_FAILURE;
   <span class="enscript-keyword">\}</span>
 
   /* set the number to 654321 (note this is bigger than 127) */
   if ((result = mp_set_int(&amp;number, 654321)) != MP_OKAY) <span class="enscript-keyword">\{</span>
      printf(&quot;Error setting the value of the number.  \%s&quot;, 
             mp_error_to_string(result));
      return EXIT_FAILURE;
   <span class="enscript-keyword">\}</span>

   printf(&quot;number == \%lu&quot;, mp_get_int(&amp;number));

   /* we're done with it. */ 
   mp_clear(&amp;number);

   return EXIT_SUCCESS;
<span class="enscript-keyword">\}</span>
<span class="enscript-keyword">\end</span>{alltt} <span class="enscript-keyword">\end</span>{small}

This should output the following if the program succeeds.

<span class="enscript-keyword">\begin</span>{alltt}
number == 654321
<span class="enscript-keyword">\end</span>{alltt}

<span class="enscript-keyword">\subsection</span>{Initialize and Setting Constants}
To both initialize and set small constants the following two functions are available.
<span class="enscript-keyword">\index</span>{mp<span class="enscript-keyword">\_</span>init<span class="enscript-keyword">\_</span>set} <span class="enscript-keyword">\index</span>{mp<span class="enscript-keyword">\_</span>init<span class="enscript-keyword">\_</span>set<span class="enscript-keyword">\_</span>int}
<span class="enscript-keyword">\begin</span>{alltt}
int mp_init_set (mp_int * a, mp_digit b);
int mp_init_set_int (mp_int * a, unsigned long b);
<span class="enscript-keyword">\end</span>{alltt}

Both functions work like the previous counterparts except they first mp<span class="enscript-keyword">\_</span>init <span class="enscript-variable-name">$a$</span> before setting the values.  

<span class="enscript-keyword">\begin</span>{alltt}
int main(void)
<span class="enscript-keyword">\{</span>
   mp_int number1, number2;
   int    result;

   /* initialize and set a single digit */
   if ((result = mp_init_set(&amp;number1, 100)) != MP_OKAY) <span class="enscript-keyword">\{</span>
      printf(&quot;Error setting number1: \%s&quot;, 
             mp_error_to_string(result));
      return EXIT_FAILURE;
   <span class="enscript-keyword">\}</span>             

   /* initialize and set a long */
   if ((result = mp_init_set_int(&amp;number2, 1023)) != MP_OKAY) <span class="enscript-keyword">\{</span>
      printf(&quot;Error setting number2: \%s&quot;, 
             mp_error_to_string(result));
      return EXIT_FAILURE;
   <span class="enscript-keyword">\}</span>

   /* display */
   printf(&quot;Number1, Number2 == \%lu, \%lu&quot;,
          mp_get_int(&amp;number1), mp_get_int(&amp;number2));

   /* clear */
   mp_clear_multi(&amp;number1, &amp;number2, NULL);

   return EXIT_SUCCESS;
<span class="enscript-keyword">\}</span>
<span class="enscript-keyword">\end</span>{alltt}

If this program succeeds it shall output.
<span class="enscript-keyword">\begin</span>{alltt}
Number1, Number2 == 100, 1023
<span class="enscript-keyword">\end</span>{alltt}

<span class="enscript-keyword">\section</span>{Comparisons}

Comparisons in LibTomMath are always performed in a ``left to right'' fashion.  There are three possible return codes
for any comparison.

<span class="enscript-keyword">\index</span>{MP<span class="enscript-keyword">\_</span>GT} <span class="enscript-keyword">\index</span>{MP<span class="enscript-keyword">\_</span>EQ} <span class="enscript-keyword">\index</span>{MP<span class="enscript-keyword">\_</span>LT}
<span class="enscript-keyword">\begin</span>{figure}[here]
<span class="enscript-keyword">\begin</span>{center}
<span class="enscript-keyword">\begin</span>{tabular}{|c|c|}
<span class="enscript-keyword">\hline</span> <span class="enscript-keyword">\textbf</span>{Result Code} &amp; <span class="enscript-keyword">\textbf</span>{Meaning} <span class="enscript-keyword">\\</span>
<span class="enscript-keyword">\hline</span> MP<span class="enscript-keyword">\_</span>GT &amp; <span class="enscript-variable-name">$a &gt; b$</span> <span class="enscript-keyword">\\</span>
<span class="enscript-keyword">\hline</span> MP<span class="enscript-keyword">\_</span>EQ &amp; <span class="enscript-variable-name">$a = b$</span> <span class="enscript-keyword">\\</span>
<span class="enscript-keyword">\hline</span> MP<span class="enscript-keyword">\_</span>LT &amp; <span class="enscript-variable-name">$a &lt; b$</span> <span class="enscript-keyword">\\</span>
<span class="enscript-keyword">\hline</span>
<span class="enscript-keyword">\end</span>{tabular}
<span class="enscript-keyword">\end</span>{center}
<span class="enscript-keyword">\caption</span>{Comparison Codes for <span class="enscript-variable-name">$a, b$</span>}
<span class="enscript-keyword">\label</span>{fig:CMP}
<span class="enscript-keyword">\end</span>{figure}

In figure <span class="enscript-keyword">\ref</span>{fig:CMP} two integers <span class="enscript-variable-name">$a$</span> and <span class="enscript-variable-name">$b$</span> are being compared.  In this case <span class="enscript-variable-name">$a$</span> is said to be ``to the left'' of 
<span class="enscript-variable-name">$b$</span>.  

<span class="enscript-keyword">\subsection</span>{Unsigned comparison}

An unsigned comparison considers only the digits themselves and not the associated <span class="enscript-keyword">\textit</span>{sign} flag of the 
mp<span class="enscript-keyword">\_</span>int structures.  This is analogous to an absolute comparison.  The function mp<span class="enscript-keyword">\_</span>cmp<span class="enscript-keyword">\_</span>mag() will compare two
mp<span class="enscript-keyword">\_</span>int variables based on their digits only. 

<span class="enscript-keyword">\index</span>{mp<span class="enscript-keyword">\_</span>cmp<span class="enscript-keyword">\_</span>mag}
<span class="enscript-keyword">\begin</span>{alltt}
int mp_cmp_mag(mp_int * a, mp_int * b);
<span class="enscript-keyword">\end</span>{alltt}
This will compare <span class="enscript-variable-name">$a$</span> to <span class="enscript-variable-name">$b$</span> placing <span class="enscript-variable-name">$a$</span> to the left of <span class="enscript-variable-name">$b$</span>.  This function cannot fail and will return one of the
three compare codes listed in figure <span class="enscript-keyword">\ref</span>{fig:CMP}.

<span class="enscript-keyword">\begin</span>{small} <span class="enscript-keyword">\begin</span>{alltt}
int main(void)
<span class="enscript-keyword">\{</span>
   mp_int number1, number2;
   int result;

   if ((result = mp_init_multi(&amp;number1, &amp;number2, NULL)) != MP_OKAY) <span class="enscript-keyword">\{</span>
      printf(&quot;Error initializing the numbers.  \%s&quot;, 
             mp_error_to_string(result));
      return EXIT_FAILURE;
   <span class="enscript-keyword">\}</span>
 
   /* set the number1 to 5 */
   mp_set(&amp;number1, 5);
  
   /* set the number2 to -6 */
   mp_set(&amp;number2, 6);
   if ((result = mp_neg(&amp;number2, &amp;number2)) != MP_OKAY) <span class="enscript-keyword">\{</span>
      printf(&quot;Error negating number2.  \%s&quot;, 
             mp_error_to_string(result));
      return EXIT_FAILURE;
   <span class="enscript-keyword">\}</span>

   switch(mp_cmp_mag(&amp;number1, &amp;number2)) <span class="enscript-keyword">\{</span>
       case MP_GT:  printf(&quot;|number1| &gt; |number2|&quot;); break;
       case MP_EQ:  printf(&quot;|number1| = |number2|&quot;); break;
       case MP_LT:  printf(&quot;|number1| &lt; |number2|&quot;); break;
   <span class="enscript-keyword">\}</span>

   /* we're done with it. */ 
   mp_clear_multi(&amp;number1, &amp;number2, NULL);

   return EXIT_SUCCESS;
<span class="enscript-keyword">\}</span>
<span class="enscript-keyword">\end</span>{alltt} <span class="enscript-keyword">\end</span>{small}

If this program<span class="enscript-keyword">\footnote</span>{This function uses the mp<span class="enscript-keyword">\_</span>neg() function which is discussed in section <span class="enscript-keyword">\ref</span>{sec:NEG}.} completes 
successfully it should print the following.

<span class="enscript-keyword">\begin</span>{alltt}
|number1| &lt; |number2|
<span class="enscript-keyword">\end</span>{alltt}

This is because <span class="enscript-variable-name">$\vert -6 \vert = 6$</span> and obviously <span class="enscript-variable-name">$5 &lt; 6$</span>.

<span class="enscript-keyword">\subsection</span>{Signed comparison}

To compare two mp<span class="enscript-keyword">\_</span>int variables based on their signed value the mp<span class="enscript-keyword">\_</span>cmp() function is provided.

<span class="enscript-keyword">\index</span>{mp<span class="enscript-keyword">\_</span>cmp}
<span class="enscript-keyword">\begin</span>{alltt}
int mp_cmp(mp_int * a, mp_int * b);
<span class="enscript-keyword">\end</span>{alltt}

This will compare <span class="enscript-variable-name">$a$</span> to the left of <span class="enscript-variable-name">$b$</span>.  It will first compare the signs of the two mp<span class="enscript-keyword">\_</span>int variables.  If they
differ it will return immediately based on their signs.  If the signs are equal then it will compare the digits
individually.  This function will return one of the compare conditions codes listed in figure <span class="enscript-keyword">\ref</span>{fig:CMP}.

<span class="enscript-keyword">\begin</span>{small} <span class="enscript-keyword">\begin</span>{alltt}
int main(void)
<span class="enscript-keyword">\{</span>
   mp_int number1, number2;
   int result;

   if ((result = mp_init_multi(&amp;number1, &amp;number2, NULL)) != MP_OKAY) <span class="enscript-keyword">\{</span>
      printf(&quot;Error initializing the numbers.  \%s&quot;, 
             mp_error_to_string(result));
      return EXIT_FAILURE;
   <span class="enscript-keyword">\}</span>
 
   /* set the number1 to 5 */
   mp_set(&amp;number1, 5);
  
   /* set the number2 to -6 */
   mp_set(&amp;number2, 6);
   if ((result = mp_neg(&amp;number2, &amp;number2)) != MP_OKAY) <span class="enscript-keyword">\{</span>
      printf(&quot;Error negating number2.  \%s&quot;, 
             mp_error_to_string(result));
      return EXIT_FAILURE;
   <span class="enscript-keyword">\}</span>

   switch(mp_cmp(&amp;number1, &amp;number2)) <span class="enscript-keyword">\{</span>
       case MP_GT:  printf(&quot;number1 &gt; number2&quot;); break;
       case MP_EQ:  printf(&quot;number1 = number2&quot;); break;
       case MP_LT:  printf(&quot;number1 &lt; number2&quot;); break;
   <span class="enscript-keyword">\}</span>

   /* we're done with it. */ 
   mp_clear_multi(&amp;number1, &amp;number2, NULL);

   return EXIT_SUCCESS;
<span class="enscript-keyword">\}</span>
<span class="enscript-keyword">\end</span>{alltt} <span class="enscript-keyword">\end</span>{small}

If this program<span class="enscript-keyword">\footnote</span>{This function uses the mp<span class="enscript-keyword">\_</span>neg() function which is discussed in section <span class="enscript-keyword">\ref</span>{sec:NEG}.} completes 
successfully it should print the following.

<span class="enscript-keyword">\begin</span>{alltt}
number1 &gt; number2
<span class="enscript-keyword">\end</span>{alltt}

<span class="enscript-keyword">\subsection</span>{Single Digit}

To compare a single digit against an mp<span class="enscript-keyword">\_</span>int the following function has been provided.

<span class="enscript-keyword">\index</span>{mp<span class="enscript-keyword">\_</span>cmp<span class="enscript-keyword">\_</span>d}
<span class="enscript-keyword">\begin</span>{alltt}
int mp_cmp_d(mp_int * a, mp_digit b);
<span class="enscript-keyword">\end</span>{alltt}

This will compare <span class="enscript-variable-name">$a$</span> to the left of <span class="enscript-variable-name">$b$</span> using a signed comparison.  Note that it will always treat <span class="enscript-variable-name">$b$</span> as 
positive.  This function is rather handy when you have to compare against small values such as <span class="enscript-variable-name">$1$</span> (which often
comes up in cryptography).  The function cannot fail and will return one of the tree compare condition codes
listed in figure <span class="enscript-keyword">\ref</span>{fig:CMP}.


<span class="enscript-keyword">\begin</span>{small} <span class="enscript-keyword">\begin</span>{alltt}
int main(void)
<span class="enscript-keyword">\{</span>
   mp_int number;
   int result;

   if ((result = mp_init(&amp;number)) != MP_OKAY) <span class="enscript-keyword">\{</span>
      printf(&quot;Error initializing the number.  \%s&quot;, 
             mp_error_to_string(result));
      return EXIT_FAILURE;
   <span class="enscript-keyword">\}</span>
 
   /* set the number to 5 */
   mp_set(&amp;number, 5);

   switch(mp_cmp_d(&amp;number, 7)) <span class="enscript-keyword">\{</span>
       case MP_GT:  printf(&quot;number &gt; 7&quot;); break;
       case MP_EQ:  printf(&quot;number = 7&quot;); break;
       case MP_LT:  printf(&quot;number &lt; 7&quot;); break;
   <span class="enscript-keyword">\}</span>

   /* we're done with it. */ 
   mp_clear(&amp;number);

   return EXIT_SUCCESS;
<span class="enscript-keyword">\}</span>
<span class="enscript-keyword">\end</span>{alltt} <span class="enscript-keyword">\end</span>{small}

If this program functions properly it will print out the following.

<span class="enscript-keyword">\begin</span>{alltt}
number &lt; 7
<span class="enscript-keyword">\end</span>{alltt}

<span class="enscript-keyword">\section</span>{Logical Operations}

Logical operations are operations that can be performed either with simple shifts or boolean operators such as
AND, XOR and OR directly.  These operations are very quick.

<span class="enscript-keyword">\subsection</span>{Multiplication by two}

Multiplications and divisions by any power of two can be performed with quick logical shifts either left or
right depending on the operation.  

When multiplying or dividing by two a special case routine can be used which are as follows.
<span class="enscript-keyword">\index</span>{mp<span class="enscript-keyword">\_</span>mul<span class="enscript-keyword">\_</span>2} <span class="enscript-keyword">\index</span>{mp<span class="enscript-keyword">\_</span>div<span class="enscript-keyword">\_</span>2}
<span class="enscript-keyword">\begin</span>{alltt}
int mp_mul_2(mp_int * a, mp_int * b);
int mp_div_2(mp_int * a, mp_int * b);
<span class="enscript-keyword">\end</span>{alltt}

The former will assign twice <span class="enscript-variable-name">$a$</span> to <span class="enscript-variable-name">$b$</span> while the latter will assign half <span class="enscript-variable-name">$a$</span> to <span class="enscript-variable-name">$b$</span>.  These functions are fast
since the shift counts and maskes are hardcoded into the routines.

<span class="enscript-keyword">\begin</span>{small} <span class="enscript-keyword">\begin</span>{alltt}
int main(void)
<span class="enscript-keyword">\{</span>
   mp_int number;
   int result;

   if ((result = mp_init(&amp;number)) != MP_OKAY) <span class="enscript-keyword">\{</span>
      printf(&quot;Error initializing the number.  \%s&quot;, 
             mp_error_to_string(result));
      return EXIT_FAILURE;
   <span class="enscript-keyword">\}</span>
 
   /* set the number to 5 */
   mp_set(&amp;number, 5);

   /* multiply by two */
   if ((result = mp<span class="enscript-keyword">\_</span>mul<span class="enscript-keyword">\_</span>2(&amp;number, &amp;number)) != MP_OKAY) <span class="enscript-keyword">\{</span>
      printf(&quot;Error multiplying the number.  \%s&quot;, 
             mp_error_to_string(result));
      return EXIT_FAILURE;
   <span class="enscript-keyword">\}</span>
   switch(mp_cmp_d(&amp;number, 7)) <span class="enscript-keyword">\{</span>
       case MP_GT:  printf(&quot;2*number &gt; 7&quot;); break;
       case MP_EQ:  printf(&quot;2*number = 7&quot;); break;
       case MP_LT:  printf(&quot;2*number &lt; 7&quot;); break;
   <span class="enscript-keyword">\}</span>

   /* now divide by two */
   if ((result = mp<span class="enscript-keyword">\_</span>div<span class="enscript-keyword">\_</span>2(&amp;number, &amp;number)) != MP_OKAY) <span class="enscript-keyword">\{</span>
      printf(&quot;Error dividing the number.  \%s&quot;, 
             mp_error_to_string(result));
      return EXIT_FAILURE;
   <span class="enscript-keyword">\}</span>
   switch(mp_cmp_d(&amp;number, 7)) <span class="enscript-keyword">\{</span>
       case MP_GT:  printf(&quot;2*number/2 &gt; 7&quot;); break;
       case MP_EQ:  printf(&quot;2*number/2 = 7&quot;); break;
       case MP_LT:  printf(&quot;2*number/2 &lt; 7&quot;); break;
   <span class="enscript-keyword">\}</span>

   /* we're done with it. */ 
   mp_clear(&amp;number);

   return EXIT_SUCCESS;
<span class="enscript-keyword">\}</span>
<span class="enscript-keyword">\end</span>{alltt} <span class="enscript-keyword">\end</span>{small}

If this program is successful it will print out the following text.

<span class="enscript-keyword">\begin</span>{alltt}
2*number &gt; 7
2*number/2 &lt; 7
<span class="enscript-keyword">\end</span>{alltt}

Since <span class="enscript-variable-name">$10 &gt; 7$</span> and <span class="enscript-variable-name">$5 &lt; 7$</span>.  To multiply by a power of two the following function can be used.

<span class="enscript-keyword">\index</span>{mp<span class="enscript-keyword">\_</span>mul<span class="enscript-keyword">\_</span>2d}
<span class="enscript-keyword">\begin</span>{alltt}
int mp_mul_2d(mp_int * a, int b, mp_int * c);
<span class="enscript-keyword">\end</span>{alltt}

This will multiply <span class="enscript-variable-name">$a$</span> by <span class="enscript-variable-name">$2^b$</span> and store the result in ``c''.  If the value of <span class="enscript-variable-name">$b$</span> is less than or equal to 
zero the function will copy <span class="enscript-variable-name">$a$</span> to ``c'' without performing any further actions.  

To divide by a power of two use the following.

<span class="enscript-keyword">\index</span>{mp<span class="enscript-keyword">\_</span>div<span class="enscript-keyword">\_</span>2d}
<span class="enscript-keyword">\begin</span>{alltt}
int mp_div_2d (mp_int * a, int b, mp_int * c, mp_int * d);
<span class="enscript-keyword">\end</span>{alltt}
Which will divide <span class="enscript-variable-name">$a$</span> by <span class="enscript-variable-name">$2^b$</span>, store the quotient in ``c'' and the remainder in ``d'.  If <span class="enscript-variable-name">$b \le 0$</span> then the
function simply copies <span class="enscript-variable-name">$a$</span> over to ``c'' and zeroes <span class="enscript-variable-name">$d$</span>.  The variable <span class="enscript-variable-name">$d$</span> may be passed as a <span class="enscript-keyword">\textbf</span>{NULL}
value to signal that the remainder is not desired.

<span class="enscript-keyword">\subsection</span>{Polynomial Basis Operations}

Strictly speaking the organization of the integers within the mp<span class="enscript-keyword">\_</span>int structures is what is known as a 
``polynomial basis''.  This simply means a field element is stored by divisions of a radix.  For example, if
<span class="enscript-variable-name">$f(x) = \sum_{i=0}^{k} y_ix^k$</span> for any vector <span class="enscript-variable-name">$\vec y$</span> then the array of digits in <span class="enscript-variable-name">$\vec y$</span> are said to be 
the polynomial basis representation of <span class="enscript-variable-name">$z$</span> if <span class="enscript-variable-name">$f(\beta) = z$</span> for a given radix <span class="enscript-variable-name">$\beta$</span>.  

To multiply by the polynomial <span class="enscript-variable-name">$g(x) = x$</span> all you have todo is shift the digits of the basis left one place.  The
following function provides this operation.

<span class="enscript-keyword">\index</span>{mp<span class="enscript-keyword">\_</span>lshd}
<span class="enscript-keyword">\begin</span>{alltt}
int mp_lshd (mp_int * a, int b);
<span class="enscript-keyword">\end</span>{alltt}

This will multiply <span class="enscript-variable-name">$a$</span> in place by <span class="enscript-variable-name">$x^b$</span> which is equivalent to shifting the digits left <span class="enscript-variable-name">$b$</span> places and inserting zeroes
in the least significant digits.  Similarly to divide by a power of <span class="enscript-variable-name">$x$</span> the following function is provided.

<span class="enscript-keyword">\index</span>{mp<span class="enscript-keyword">\_</span>rshd}
<span class="enscript-keyword">\begin</span>{alltt}
void mp_rshd (mp_int * a, int b)
<span class="enscript-keyword">\end</span>{alltt}
This will divide <span class="enscript-variable-name">$a$</span> in place by <span class="enscript-variable-name">$x^b$</span> and discard the remainder.  This function cannot fail as it performs the operations
in place and no new digits are required to complete it.

<span class="enscript-keyword">\subsection</span>{AND, OR and XOR Operations}

While AND, OR and XOR operations are not typical ``bignum functions'' they can be useful in several instances.  The
three functions are prototyped as follows.

<span class="enscript-keyword">\index</span>{mp<span class="enscript-keyword">\_</span>or} <span class="enscript-keyword">\index</span>{mp<span class="enscript-keyword">\_</span>and} <span class="enscript-keyword">\index</span>{mp<span class="enscript-keyword">\_</span>xor}
<span class="enscript-keyword">\begin</span>{alltt}
int mp_or  (mp_int * a, mp_int * b, mp_int * c);
int mp_and (mp_int * a, mp_int * b, mp_int * c);
int mp_xor (mp_int * a, mp_int * b, mp_int * c);
<span class="enscript-keyword">\end</span>{alltt}

Which compute <span class="enscript-variable-name">$c = a \odot b$</span> where <span class="enscript-variable-name">$\odot$</span> is one of OR, AND or XOR.  

<span class="enscript-keyword">\section</span>{Addition and Subtraction}

To compute an addition or subtraction the following two functions can be used.

<span class="enscript-keyword">\index</span>{mp<span class="enscript-keyword">\_</span>add} <span class="enscript-keyword">\index</span>{mp<span class="enscript-keyword">\_</span>sub}
<span class="enscript-keyword">\begin</span>{alltt}
int mp_add (mp_int * a, mp_int * b, mp_int * c);
int mp_sub (mp_int * a, mp_int * b, mp_int * c)
<span class="enscript-keyword">\end</span>{alltt}

Which perform <span class="enscript-variable-name">$c = a \odot b$</span> where <span class="enscript-variable-name">$\odot$</span> is one of signed addition or subtraction.  The operations are fully sign
aware.

<span class="enscript-keyword">\section</span>{Sign Manipulation}
<span class="enscript-keyword">\subsection</span>{Negation}
<span class="enscript-keyword">\label</span>{sec:NEG}
Simple integer negation can be performed with the following.

<span class="enscript-keyword">\index</span>{mp<span class="enscript-keyword">\_</span>neg}
<span class="enscript-keyword">\begin</span>{alltt}
int mp_neg (mp_int * a, mp_int * b);
<span class="enscript-keyword">\end</span>{alltt}

Which assigns <span class="enscript-variable-name">$-a$</span> to <span class="enscript-variable-name">$b$</span>.  

<span class="enscript-keyword">\subsection</span>{Absolute}
Simple integer absolutes can be performed with the following.

<span class="enscript-keyword">\index</span>{mp<span class="enscript-keyword">\_</span>neg}
<span class="enscript-keyword">\begin</span>{alltt}
int mp_abs (mp_int * a, mp_int * b);
<span class="enscript-keyword">\end</span>{alltt}

Which assigns <span class="enscript-variable-name">$\vert a \vert$</span> to <span class="enscript-variable-name">$b$</span>.  

<span class="enscript-keyword">\section</span>{Integer Division and Remainder}
To perform a complete and general integer division with remainder use the following function.

<span class="enscript-keyword">\index</span>{mp<span class="enscript-keyword">\_</span>div}
<span class="enscript-keyword">\begin</span>{alltt}
int mp_div (mp_int * a, mp_int * b, mp_int * c, mp_int * d);
<span class="enscript-keyword">\end</span>{alltt}
                                                        
This divides <span class="enscript-variable-name">$a$</span> by <span class="enscript-variable-name">$b$</span> and stores the quotient in <span class="enscript-variable-name">$c$</span> and <span class="enscript-variable-name">$d$</span>.  The signed quotient is computed such that 
<span class="enscript-variable-name">$bc + d = a$</span>.  Note that either of <span class="enscript-variable-name">$c$</span> or <span class="enscript-variable-name">$d$</span> can be set to <span class="enscript-keyword">\textbf</span>{NULL} if their value is not required.  If 
<span class="enscript-variable-name">$b$</span> is zero the function returns <span class="enscript-keyword">\textbf</span>{MP<span class="enscript-keyword">\_</span>VAL}.  


<span class="enscript-keyword">\chapter</span>{Multiplication and Squaring}
<span class="enscript-keyword">\section</span>{Multiplication}
A full signed integer multiplication can be performed with the following.
<span class="enscript-keyword">\index</span>{mp<span class="enscript-keyword">\_</span>mul}
<span class="enscript-keyword">\begin</span>{alltt}
int mp_mul (mp_int * a, mp_int * b, mp_int * c);
<span class="enscript-keyword">\end</span>{alltt}
Which assigns the full signed product <span class="enscript-variable-name">$ab$</span> to <span class="enscript-variable-name">$c$</span>.  This function actually breaks into one of four cases which are 
specific multiplication routines optimized for given parameters.  First there are the Toom-Cook multiplications which
should only be used with very large inputs.  This is followed by the Karatsuba multiplications which are for moderate
sized inputs.  Then followed by the Comba and baseline multipliers.

Fortunately for the developer you don't really need to know this unless you really want to fine tune the system.  mp<span class="enscript-keyword">\_</span>mul()
will determine on its own<span class="enscript-keyword">\footnote</span>{Some tweaking may be required.} what routine to use automatically when it is called.

<span class="enscript-keyword">\begin</span>{alltt}
int main(void)
<span class="enscript-keyword">\{</span>
   mp_int number1, number2;
   int result;

   /* Initialize the numbers */
   if ((result = mp_init_multi(&amp;number1, 
                               &amp;number2, NULL)) != MP_OKAY) <span class="enscript-keyword">\{</span>
      printf(&quot;Error initializing the numbers.  \%s&quot;, 
             mp_error_to_string(result));
      return EXIT_FAILURE;
   <span class="enscript-keyword">\}</span>

   /* set the terms */
   if ((result = mp_set_int(&amp;number, 257)) != MP_OKAY) <span class="enscript-keyword">\{</span>
      printf(&quot;Error setting number1.  \%s&quot;, 
             mp_error_to_string(result));
      return EXIT_FAILURE;
   <span class="enscript-keyword">\}</span>
 
   if ((result = mp_set_int(&amp;number2, 1023)) != MP_OKAY) <span class="enscript-keyword">\{</span>
      printf(&quot;Error setting number2.  \%s&quot;, 
             mp_error_to_string(result));
      return EXIT_FAILURE;
   <span class="enscript-keyword">\}</span>

   /* multiply them */
   if ((result = mp_mul(&amp;number1, &amp;number2,
                        &amp;number1)) != MP_OKAY) <span class="enscript-keyword">\{</span>
      printf(&quot;Error multiplying terms.  \%s&quot;, 
             mp_error_to_string(result));
      return EXIT_FAILURE;
   <span class="enscript-keyword">\}</span>

   /* display */
   printf(&quot;number1 * number2 == \%lu&quot;, mp_get_int(&amp;number1));

   /* free terms and return */
   mp_clear_multi(&amp;number1, &amp;number2, NULL);

   return EXIT_SUCCESS;
<span class="enscript-keyword">\}</span>
<span class="enscript-keyword">\end</span>{alltt}   

If this program succeeds it shall output the following.

<span class="enscript-keyword">\begin</span>{alltt}
number1 * number2 == 262911
<span class="enscript-keyword">\end</span>{alltt}

<span class="enscript-keyword">\section</span>{Squaring}
Since squaring can be performed faster than multiplication it is performed it's own function instead of just using
mp<span class="enscript-keyword">\_</span>mul().

<span class="enscript-keyword">\index</span>{mp<span class="enscript-keyword">\_</span>sqr}
<span class="enscript-keyword">\begin</span>{alltt}
int mp_sqr (mp_int * a, mp_int * b);
<span class="enscript-keyword">\end</span>{alltt}

Will square <span class="enscript-variable-name">$a$</span> and store it in <span class="enscript-variable-name">$b$</span>.  Like the case of multiplication there are four different squaring
algorithms all which can be called from mp<span class="enscript-keyword">\_</span>sqr().  It is ideal to use mp<span class="enscript-keyword">\_</span>sqr over mp<span class="enscript-keyword">\_</span>mul when squaring terms because
of the speed difference.  

<span class="enscript-keyword">\section</span>{Tuning Polynomial Basis Routines}

Both of the Toom-Cook and Karatsuba multiplication algorithms are faster than the traditional <span class="enscript-variable-name">$O(n^2)$</span> approach that
the Comba and baseline algorithms use.  At <span class="enscript-variable-name">$O(n^{1.464973})$</span> and <span class="enscript-variable-name">$O(n^{1.584962})$</span> running times respectively they require 
considerably less work.  For example, a 10000-digit multiplication would take roughly 724,000 single precision
multiplications with Toom-Cook or 100,000,000 single precision multiplications with the standard Comba (a factor
of 138).

So why not always use Karatsuba or Toom-Cook?   The simple answer is that they have so much overhead that they're not
actually faster than Comba until you hit distinct  ``cutoff'' points.  For Karatsuba with the default configuration, 
GCC 3.3.1 and an Athlon XP processor the cutoff point is roughly 110 digits (about 70 for the Intel P4).  That is, at 
110 digits Karatsuba and Comba multiplications just about break even and for 110+ digits Karatsuba is faster.

Toom-Cook has incredible overhead and is probably only useful for very large inputs.  So far no known cutoff points 
exist and for the most part I just set the cutoff points very high to make sure they're not called.

A demo program in the ``etc/'' directory of the project called ``tune.c'' can be used to find the cutoff points.  This
can be built with GCC as follows

<span class="enscript-keyword">\begin</span>{alltt}
make XXX
<span class="enscript-keyword">\end</span>{alltt}
Where ``XXX'' is one of the following entries from the table <span class="enscript-keyword">\ref</span>{fig:tuning}.

<span class="enscript-keyword">\begin</span>{figure}[here]
<span class="enscript-keyword">\begin</span>{center}
<span class="enscript-keyword">\begin</span>{small}
<span class="enscript-keyword">\begin</span>{tabular}{|l|l|}
<span class="enscript-keyword">\hline</span> <span class="enscript-keyword">\textbf</span>{Value of XXX} &amp; <span class="enscript-keyword">\textbf</span>{Meaning} <span class="enscript-keyword">\\</span>
<span class="enscript-keyword">\hline</span> tune &amp; Builds portable tuning application <span class="enscript-keyword">\\</span>
<span class="enscript-keyword">\hline</span> tune86 &amp; Builds x86 (pentium and up) program for COFF <span class="enscript-keyword">\\</span>
<span class="enscript-keyword">\hline</span> tune86c &amp; Builds x86 program for Cygwin <span class="enscript-keyword">\\</span>
<span class="enscript-keyword">\hline</span> tune86l &amp; Builds x86 program for Linux (ELF format) <span class="enscript-keyword">\\</span>
<span class="enscript-keyword">\hline</span>
<span class="enscript-keyword">\end</span>{tabular}
<span class="enscript-keyword">\end</span>{small}
<span class="enscript-keyword">\end</span>{center}
<span class="enscript-keyword">\caption</span>{Build Names for Tuning Programs}
<span class="enscript-keyword">\label</span>{fig:tuning}
<span class="enscript-keyword">\end</span>{figure}

When the program is running it will output a series of measurements for different cutoff points.  It will first find
good Karatsuba squaring and multiplication points.  Then it proceeds to find Toom-Cook points.  Note that the Toom-Cook
tuning takes a very long time as the cutoff points are likely to be very high.

<span class="enscript-keyword">\chapter</span>{Modular Reduction}

Modular reduction is process of taking the remainder of one quantity divided by another.  Expressed 
as (<span class="enscript-keyword">\ref</span>{eqn:mod}) the modular reduction is equivalent to the remainder of <span class="enscript-variable-name">$b$</span> divided by <span class="enscript-variable-name">$c$</span>.  

<span class="enscript-keyword">\begin</span>{equation}
a <span class="enscript-keyword">\equiv</span> b <span class="enscript-keyword">\mbox</span>{ (mod }c<span class="enscript-keyword">\mbox</span>{)}
<span class="enscript-keyword">\label</span>{eqn:mod}
<span class="enscript-keyword">\end</span>{equation}

Of particular interest to cryptography are reductions where <span class="enscript-variable-name">$b$</span> is limited to the range <span class="enscript-variable-name">$0 \le b &lt; c^2$</span> since particularly 
fast reduction algorithms can be written for the limited range.  

Note that one of the four optimized reduction algorithms are automatically chosen in the modular exponentiation
algorithm mp<span class="enscript-keyword">\_</span>exptmod when an appropriate modulus is detected.  

<span class="enscript-keyword">\section</span>{Straight Division}
In order to effect an arbitrary modular reduction the following algorithm is provided.

<span class="enscript-keyword">\index</span>{mp<span class="enscript-keyword">\_</span>mod}
<span class="enscript-keyword">\begin</span>{alltt}
int mp_mod(mp_int *a, mp_int *b, mp_int *c);
<span class="enscript-keyword">\end</span>{alltt}

This reduces <span class="enscript-variable-name">$a$</span> modulo <span class="enscript-variable-name">$b$</span> and stores the result in <span class="enscript-variable-name">$c$</span>.  The sign of <span class="enscript-variable-name">$c$</span> shall agree with the sign 
of <span class="enscript-variable-name">$b$</span>.  This algorithm accepts an input <span class="enscript-variable-name">$a$</span> of any range and is not limited by <span class="enscript-variable-name">$0 \le a &lt; b^2$</span>.

<span class="enscript-keyword">\section</span>{Barrett Reduction}

Barrett reduction is a generic optimized reduction algorithm that requires pre--computation to achieve
a decent speedup over straight division.  First a <span class="enscript-variable-name">$\mu$</span> value must be precomputed with the following function.

<span class="enscript-keyword">\index</span>{mp<span class="enscript-keyword">\_</span>reduce<span class="enscript-keyword">\_</span>setup}
<span class="enscript-keyword">\begin</span>{alltt}
int mp_reduce_setup(mp_int *a, mp_int *b);
<span class="enscript-keyword">\end</span>{alltt}

Given a modulus in <span class="enscript-variable-name">$b$</span> this produces the required <span class="enscript-variable-name">$\mu$</span> value in <span class="enscript-variable-name">$a$</span>.  For any given modulus this only has to
be computed once.  Modular reduction can now be performed with the following.

<span class="enscript-keyword">\index</span>{mp<span class="enscript-keyword">\_</span>reduce}
<span class="enscript-keyword">\begin</span>{alltt}
int mp_reduce(mp_int *a, mp_int *b, mp_int *c);
<span class="enscript-keyword">\end</span>{alltt}

This will reduce <span class="enscript-variable-name">$a$</span> in place modulo <span class="enscript-variable-name">$b$</span> with the precomputed <span class="enscript-variable-name">$\mu$</span> value in <span class="enscript-variable-name">$c$</span>.  <span class="enscript-variable-name">$a$</span> must be in the range
<span class="enscript-variable-name">$0 \le a &lt; b^2$</span>.

<span class="enscript-keyword">\begin</span>{alltt}
int main(void)
<span class="enscript-keyword">\{</span>
   mp_int   a, b, c, mu;
   int      result;

   /* initialize a,b to desired values, mp_init mu, 
    * c and set c to 1...we want to compute a^3 mod b 
    */

   /* get mu value */
   if ((result = mp_reduce_setup(&amp;mu, b)) != MP_OKAY) <span class="enscript-keyword">\{</span>
      printf(&quot;Error getting mu.  \%s&quot;, 
             mp_error_to_string(result));
      return EXIT_FAILURE;
   <span class="enscript-keyword">\}</span>

   /* square a to get c = a^2 */
   if ((result = mp_sqr(&amp;a, &amp;c)) != MP_OKAY) <span class="enscript-keyword">\{</span>
      printf(&quot;Error squaring.  \%s&quot;, 
             mp_error_to_string(result));
      return EXIT_FAILURE;
   <span class="enscript-keyword">\}</span>

   /* now reduce `c' modulo b */
   if ((result = mp_reduce(&amp;c, &amp;b, &amp;mu)) != MP_OKAY) <span class="enscript-keyword">\{</span>
      printf(&quot;Error reducing.  \%s&quot;, 
             mp_error_to_string(result));
      return EXIT_FAILURE;
   <span class="enscript-keyword">\}</span>
   
   /* multiply a to get c = a^3 */
   if ((result = mp_mul(&amp;a, &amp;c, &amp;c)) != MP_OKAY) <span class="enscript-keyword">\{</span>
      printf(&quot;Error reducing.  \%s&quot;, 
             mp_error_to_string(result));
      return EXIT_FAILURE;
   <span class="enscript-keyword">\}</span>

   /* now reduce `c' modulo b  */
   if ((result = mp_reduce(&amp;c, &amp;b, &amp;mu)) != MP_OKAY) <span class="enscript-keyword">\{</span>
      printf(&quot;Error reducing.  \%s&quot;, 
             mp_error_to_string(result));
      return EXIT_FAILURE;
   <span class="enscript-keyword">\}</span>
  
   /* c now equals a^3 mod b */

   return EXIT_SUCCESS;
<span class="enscript-keyword">\}</span>
<span class="enscript-keyword">\end</span>{alltt} 

This program will calculate <span class="enscript-variable-name">$a^3 \mbox{ mod }b$</span> if all the functions succeed.  

<span class="enscript-keyword">\section</span>{Montgomery Reduction}

Montgomery is a specialized reduction algorithm for any odd moduli.  Like Barrett reduction a pre--computation
step is required.  This is accomplished with the following.

<span class="enscript-keyword">\index</span>{mp<span class="enscript-keyword">\_</span>montgomery<span class="enscript-keyword">\_</span>setup}
<span class="enscript-keyword">\begin</span>{alltt}
int mp_montgomery_setup(mp_int *a, mp_digit *mp);
<span class="enscript-keyword">\end</span>{alltt}

For the given odd moduli <span class="enscript-variable-name">$a$</span> the precomputation value is placed in <span class="enscript-variable-name">$mp$</span>.  The reduction is computed with the 
following.

<span class="enscript-keyword">\index</span>{mp<span class="enscript-keyword">\_</span>montgomery<span class="enscript-keyword">\_</span>reduce}
<span class="enscript-keyword">\begin</span>{alltt}
int mp_montgomery_reduce(mp_int *a, mp_int *m, mp_digit mp);
<span class="enscript-keyword">\end</span>{alltt}
This reduces <span class="enscript-variable-name">$a$</span> in place modulo <span class="enscript-variable-name">$m$</span> with the pre--computed value <span class="enscript-variable-name">$mp$</span>.   <span class="enscript-variable-name">$a$</span> must be in the range
<span class="enscript-variable-name">$0 \le a &lt; b^2$</span>.

Montgomery reduction is faster than Barrett reduction for moduli smaller than the ``comba'' limit.  With the default
setup for instance, the limit is <span class="enscript-variable-name">$127$</span> digits (<span class="enscript-variable-name">$3556$</span>--bits).   Note that this function is not limited to
<span class="enscript-variable-name">$127$</span> digits just that it falls back to a baseline algorithm after that point.  

An important observation is that this reduction does not return <span class="enscript-variable-name">$a \mbox{ mod }m$</span> but <span class="enscript-variable-name">$aR^{-1} \mbox{ mod }m$</span> 
where <span class="enscript-variable-name">$R = \beta^n$</span>, <span class="enscript-variable-name">$n$</span> is the n number of digits in <span class="enscript-variable-name">$m$</span> and <span class="enscript-variable-name">$\beta$</span> is radix used (default is <span class="enscript-variable-name">$2^{28}$</span>).  

To quickly calculate <span class="enscript-variable-name">$R$</span> the following function was provided.

<span class="enscript-keyword">\index</span>{mp<span class="enscript-keyword">\_</span>montgomery<span class="enscript-keyword">\_</span>calc<span class="enscript-keyword">\_</span>normalization}
<span class="enscript-keyword">\begin</span>{alltt}
int mp_montgomery_calc_normalization(mp_int *a, mp_int *b);
<span class="enscript-keyword">\end</span>{alltt}
Which calculates <span class="enscript-variable-name">$a = R$</span> for the odd moduli <span class="enscript-variable-name">$b$</span> without using multiplication or division.  

The normal modus operandi for Montgomery reductions is to normalize the integers before entering the system.  For
example, to calculate <span class="enscript-variable-name">$a^3 \mbox { mod }b$</span> using Montgomery reduction the value of <span class="enscript-variable-name">$a$</span> can be normalized by
multiplying it by <span class="enscript-variable-name">$R$</span>.  Consider the following code snippet.

<span class="enscript-keyword">\begin</span>{alltt}
int main(void)
<span class="enscript-keyword">\{</span>
   mp_int   a, b, c, R;
   mp_digit mp;
   int      result;

   /* initialize a,b to desired values, 
    * mp_init R, c and set c to 1.... 
    */

   /* get normalization */
   if ((result = mp_montgomery_calc_normalization(&amp;R, b)) != MP_OKAY) <span class="enscript-keyword">\{</span>
      printf(&quot;Error getting norm.  \%s&quot;, 
             mp_error_to_string(result));
      return EXIT_FAILURE;
   <span class="enscript-keyword">\}</span>

   /* get mp value */
   if ((result = mp_montgomery_setup(&amp;c, &amp;mp)) != MP_OKAY) <span class="enscript-keyword">\{</span>
      printf(&quot;Error setting up montgomery.  \%s&quot;, 
             mp_error_to_string(result));
      return EXIT_FAILURE;
   <span class="enscript-keyword">\}</span>

   /* normalize `a' so now a is equal to aR */
   if ((result = mp_mulmod(&amp;a, &amp;R, &amp;b, &amp;a)) != MP_OKAY) <span class="enscript-keyword">\{</span>
      printf(&quot;Error computing aR.  \%s&quot;, 
             mp_error_to_string(result));
      return EXIT_FAILURE;
   <span class="enscript-keyword">\}</span>

   /* square a to get c = a^2R^2 */
   if ((result = mp_sqr(&amp;a, &amp;c)) != MP_OKAY) <span class="enscript-keyword">\{</span>
      printf(&quot;Error squaring.  \%s&quot;, 
             mp_error_to_string(result));
      return EXIT_FAILURE;
   <span class="enscript-keyword">\}</span>

   /* now reduce `c' back down to c = a^2R^2 * R^-1 == a^2R */
   if ((result = mp_montgomery_reduce(&amp;c, &amp;b, mp)) != MP_OKAY) <span class="enscript-keyword">\{</span>
      printf(&quot;Error reducing.  \%s&quot;, 
             mp_error_to_string(result));
      return EXIT_FAILURE;
   <span class="enscript-keyword">\}</span>
   
   /* multiply a to get c = a^3R^2 */
   if ((result = mp_mul(&amp;a, &amp;c, &amp;c)) != MP_OKAY) <span class="enscript-keyword">\{</span>
      printf(&quot;Error reducing.  \%s&quot;, 
             mp_error_to_string(result));
      return EXIT_FAILURE;
   <span class="enscript-keyword">\}</span>

   /* now reduce `c' back down to c = a^3R^2 * R^-1 == a^3R */
   if ((result = mp_montgomery_reduce(&amp;c, &amp;b, mp)) != MP_OKAY) <span class="enscript-keyword">\{</span>
      printf(&quot;Error reducing.  \%s&quot;, 
             mp_error_to_string(result));
      return EXIT_FAILURE;
   <span class="enscript-keyword">\}</span>
   
   /* now reduce (again) `c' back down to c = a^3R * R^-1 == a^3 */
   if ((result = mp_montgomery_reduce(&amp;c, &amp;b, mp)) != MP_OKAY) <span class="enscript-keyword">\{</span>
      printf(&quot;Error reducing.  \%s&quot;, 
             mp_error_to_string(result));
      return EXIT_FAILURE;
   <span class="enscript-keyword">\}</span>

   /* c now equals a^3 mod b */

   return EXIT_SUCCESS;
<span class="enscript-keyword">\}</span>
<span class="enscript-keyword">\end</span>{alltt} 

This particular example does not look too efficient but it demonstrates the point of the algorithm.  By 
normalizing the inputs the reduced results are always of the form <span class="enscript-variable-name">$aR$</span> for some variable <span class="enscript-variable-name">$a$</span>.  This allows
a single final reduction to correct for the normalization and the fast reduction used within the algorithm.

For more details consider examining the file <span class="enscript-keyword">\textit</span>{bn<span class="enscript-keyword">\_</span>mp<span class="enscript-keyword">\_</span>exptmod<span class="enscript-keyword">\_</span>fast.c}.

<span class="enscript-keyword">\section</span>{Restricted Dimminished Radix}

``Dimminished Radix'' reduction refers to reduction with respect to moduli that are ameniable to simple
digit shifting and small multiplications.  In this case the ``restricted'' variant refers to moduli of the
form <span class="enscript-variable-name">$\beta^k - p$</span> for some <span class="enscript-variable-name">$k \ge 0$</span> and <span class="enscript-variable-name">$0 &lt; p &lt; \beta$</span> where <span class="enscript-variable-name">$\beta$</span> is the radix (default to <span class="enscript-variable-name">$2^{28}$</span>).  

As in the case of Montgomery reduction there is a pre--computation phase required for a given modulus.

<span class="enscript-keyword">\index</span>{mp<span class="enscript-keyword">\_</span>dr<span class="enscript-keyword">\_</span>setup}
<span class="enscript-keyword">\begin</span>{alltt}
void mp_dr_setup(mp_int *a, mp_digit *d);
<span class="enscript-keyword">\end</span>{alltt}

This computes the value required for the modulus <span class="enscript-variable-name">$a$</span> and stores it in <span class="enscript-variable-name">$d$</span>.  This function cannot fail
and does not return any error codes.  After the pre--computation a reduction can be performed with the
following.

<span class="enscript-keyword">\index</span>{mp<span class="enscript-keyword">\_</span>dr<span class="enscript-keyword">\_</span>reduce}
<span class="enscript-keyword">\begin</span>{alltt}
int mp_dr_reduce(mp_int *a, mp_int *b, mp_digit mp);
<span class="enscript-keyword">\end</span>{alltt}

This reduces <span class="enscript-variable-name">$a$</span> in place modulo <span class="enscript-variable-name">$b$</span> with the pre--computed value <span class="enscript-variable-name">$mp$</span>.  <span class="enscript-variable-name">$b$</span> must be of a restricted
dimminished radix form and <span class="enscript-variable-name">$a$</span> must be in the range <span class="enscript-variable-name">$0 \le a &lt; b^2$</span>.  Dimminished radix reductions are 
much faster than both Barrett and Montgomery reductions as they have a much lower asymtotic running time.  

Since the moduli are restricted this algorithm is not particularly useful for something like Rabin, RSA or
BBS cryptographic purposes.  This reduction algorithm is useful for Diffie-Hellman and ECC where fixed
primes are acceptable.  

Note that unlike Montgomery reduction there is no normalization process.  The result of this function is
equal to the correct residue.

<span class="enscript-keyword">\section</span>{Unrestricted Dimminshed Radix}

Unrestricted reductions work much like the restricted counterparts except in this case the moduli is of the 
form <span class="enscript-variable-name">$2^k - p$</span> for <span class="enscript-variable-name">$0 &lt; p &lt; \beta$</span>.  In this sense the unrestricted reductions are more flexible as they 
can be applied to a wider range of numbers.  

<span class="enscript-keyword">\index</span>{mp<span class="enscript-keyword">\_</span>reduce<span class="enscript-keyword">\_</span>2k<span class="enscript-keyword">\_</span>setup}
<span class="enscript-keyword">\begin</span>{alltt}
int mp_reduce_2k_setup(mp_int *a, mp_digit *d);
<span class="enscript-keyword">\end</span>{alltt}

This will compute the required <span class="enscript-variable-name">$d$</span> value for the given moduli <span class="enscript-variable-name">$a$</span>.  

<span class="enscript-keyword">\index</span>{mp<span class="enscript-keyword">\_</span>reduce<span class="enscript-keyword">\_</span>2k}
<span class="enscript-keyword">\begin</span>{alltt}
int mp_reduce_2k(mp_int *a, mp_int *n, mp_digit d);
<span class="enscript-keyword">\end</span>{alltt}

This will reduce <span class="enscript-variable-name">$a$</span> in place modulo <span class="enscript-variable-name">$n$</span> with the pre--computed value <span class="enscript-variable-name">$d$</span>.  From my experience this routine is 
slower than mp<span class="enscript-keyword">\_</span>dr<span class="enscript-keyword">\_</span>reduce but faster for most moduli sizes than the Montgomery reduction.  

<span class="enscript-keyword">\chapter</span>{Exponentiation}
<span class="enscript-keyword">\section</span>{Single Digit Exponentiation}
<span class="enscript-keyword">\index</span>{mp<span class="enscript-keyword">\_</span>expt<span class="enscript-keyword">\_</span>d}
<span class="enscript-keyword">\begin</span>{alltt}
int mp_expt_d (mp_int * a, mp_digit b, mp_int * c)
<span class="enscript-keyword">\end</span>{alltt}
This computes <span class="enscript-variable-name">$c = a^b$</span> using a simple binary left-to-right algorithm.  It is faster than repeated multiplications by 
<span class="enscript-variable-name">$a$</span> for all values of <span class="enscript-variable-name">$b$</span> greater than three.  

<span class="enscript-keyword">\section</span>{Modular Exponentiation}
<span class="enscript-keyword">\index</span>{mp<span class="enscript-keyword">\_</span>exptmod}
<span class="enscript-keyword">\begin</span>{alltt}
int mp_exptmod (mp_int * G, mp_int * X, mp_int * P, mp_int * Y)
<span class="enscript-keyword">\end</span>{alltt}
This computes <span class="enscript-variable-name">$Y \equiv G^X \mbox{ (mod }P\mbox{)}$</span> using a variable width sliding window algorithm.  This function
will automatically detect the fastest modular reduction technique to use during the operation.  For negative values of 
<span class="enscript-variable-name">$X$</span> the operation is performed as <span class="enscript-variable-name">$Y \equiv (G^{-1} \mbox{ mod }P)^{\vert X \vert} \mbox{ (mod }P\mbox{)}$</span> provided that 
<span class="enscript-variable-name">$gcd(G, P) = 1$</span>.

This function is actually a shell around the two internal exponentiation functions.  This routine will automatically
detect when Barrett, Montgomery, Restricted and Unrestricted Dimminished Radix based exponentiation can be used.  Generally
moduli of the a ``restricted dimminished radix'' form lead to the fastest modular exponentiations.  Followed by Montgomery
and the other two algorithms.

<span class="enscript-keyword">\section</span>{Root Finding}
<span class="enscript-keyword">\index</span>{mp<span class="enscript-keyword">\_</span>n<span class="enscript-keyword">\_</span>root}
<span class="enscript-keyword">\begin</span>{alltt}
int mp_n_root (mp_int * a, mp_digit b, mp_int * c)
<span class="enscript-keyword">\end</span>{alltt}
This computes <span class="enscript-variable-name">$c = a^{1/b}$</span> such that <span class="enscript-variable-name">$c^b \le a$</span> and <span class="enscript-variable-name">$(c+1)^b &gt; a$</span>.  The implementation of this function is not 
ideal for values of <span class="enscript-variable-name">$b$</span> greater than three.  It will work but become very slow.  So unless you are working with very small
numbers (less than 1000 bits) I'd avoid <span class="enscript-variable-name">$b &gt; 3$</span> situations.  Will return a positive root only for even roots and return
a root with the sign of the input for odd roots.  For example, performing <span class="enscript-variable-name">$4^{1/2}$</span> will return <span class="enscript-variable-name">$2$</span> whereas <span class="enscript-variable-name">$(-8)^{1/3}$</span> 
will return <span class="enscript-variable-name">$-2$</span>.  

This algorithm uses the ``Newton Approximation'' method and will converge on the correct root fairly quickly.  Since
the algorithm requires raising <span class="enscript-variable-name">$a$</span> to the power of <span class="enscript-variable-name">$b$</span> it is not ideal to attempt to find roots for large
values of <span class="enscript-variable-name">$b$</span>.  If particularly large roots are required then a factor method could be used instead.  For example,
<span class="enscript-variable-name">$a^{1/16}$</span> is equivalent to <span class="enscript-variable-name">$\left (a^{1/4} \right)^{1/4}$</span> or simply 
<span class="enscript-variable-name">$\left ( \left ( \left ( a^{1/2} \right )^{1/2} \right )^{1/2} \right )^{1/2}$</span>

<span class="enscript-keyword">\chapter</span>{Prime Numbers}
<span class="enscript-keyword">\section</span>{Trial Division}
<span class="enscript-keyword">\index</span>{mp<span class="enscript-keyword">\_</span>prime<span class="enscript-keyword">\_</span>is<span class="enscript-keyword">\_</span>divisible}
<span class="enscript-keyword">\begin</span>{alltt}
int mp_prime_is_divisible (mp_int * a, int *result)
<span class="enscript-keyword">\end</span>{alltt}
This will attempt to evenly divide <span class="enscript-variable-name">$a$</span> by a list of primes<span class="enscript-keyword">\footnote</span>{Default is the first 256 primes.} and store the 
outcome in ``result''.  That is if <span class="enscript-variable-name">$result = 0$</span> then <span class="enscript-variable-name">$a$</span> is not divisible by the primes, otherwise it is.  Note that 
if the function does not return <span class="enscript-keyword">\textbf</span>{MP<span class="enscript-keyword">\_</span>OKAY} the value in ``result'' should be considered undefined<span class="enscript-keyword">\footnote</span>{Currently
the default is to set it to zero first.}.

<span class="enscript-keyword">\section</span>{Fermat Test}
<span class="enscript-keyword">\index</span>{mp<span class="enscript-keyword">\_</span>prime<span class="enscript-keyword">\_</span>fermat}
<span class="enscript-keyword">\begin</span>{alltt}
int mp_prime_fermat (mp_int * a, mp_int * b, int *result)
<span class="enscript-keyword">\end</span>{alltt}
Performs a Fermat primality test to the base <span class="enscript-variable-name">$b$</span>.  That is it computes <span class="enscript-variable-name">$b^a \mbox{ mod }a$</span> and tests whether the value is
equal to <span class="enscript-variable-name">$b$</span> or not.  If the values are equal then <span class="enscript-variable-name">$a$</span> is probably prime and <span class="enscript-variable-name">$result$</span> is set to one.  Otherwise <span class="enscript-variable-name">$result$</span>
is set to zero.

<span class="enscript-keyword">\section</span>{Miller-Rabin Test}
<span class="enscript-keyword">\index</span>{mp<span class="enscript-keyword">\_</span>prime<span class="enscript-keyword">\_</span>miller<span class="enscript-keyword">\_</span>rabin}
<span class="enscript-keyword">\begin</span>{alltt}
int mp_prime_miller_rabin (mp_int * a, mp_int * b, int *result)
<span class="enscript-keyword">\end</span>{alltt}
Performs a Miller-Rabin test to the base <span class="enscript-variable-name">$b$</span> of <span class="enscript-variable-name">$a$</span>.  This test is much stronger than the Fermat test and is very hard to
fool (besides with Carmichael numbers).  If <span class="enscript-variable-name">$a$</span> passes the test (therefore is probably prime) <span class="enscript-variable-name">$result$</span> is set to one.  
Otherwise <span class="enscript-variable-name">$result$</span> is set to zero.  

Note that is suggested that you use the Miller-Rabin test instead of the Fermat test since all of the failures of 
Miller-Rabin are a subset of the failures of the Fermat test.

<span class="enscript-keyword">\subsection</span>{Required Number of Tests}
Generally to ensure a number is very likely to be prime you have to perform the Miller-Rabin with at least a half-dozen
or so unique bases.  However, it has been proven that the probability of failure goes down as the size of the input goes up.
This is why a simple function has been provided to help out.

<span class="enscript-keyword">\index</span>{mp<span class="enscript-keyword">\_</span>prime<span class="enscript-keyword">\_</span>rabin<span class="enscript-keyword">\_</span>miller<span class="enscript-keyword">\_</span>trials}
<span class="enscript-keyword">\begin</span>{alltt}
int mp_prime_rabin_miller_trials(int size)
<span class="enscript-keyword">\end</span>{alltt}
This returns the number of trials required for a <span class="enscript-variable-name">$2^{-96}$</span> (or lower) probability of failure for a given ``size'' expressed
in bits.  This comes in handy specially since larger numbers are slower to test.  For example, a 512-bit number would
require ten tests whereas a 1024-bit number would only require four tests. 

You should always still perform a trial division before a Miller-Rabin test though.

<span class="enscript-keyword">\section</span>{Primality Testing}
<span class="enscript-keyword">\index</span>{mp<span class="enscript-keyword">\_</span>prime<span class="enscript-keyword">\_</span>is<span class="enscript-keyword">\_</span>prime}
<span class="enscript-keyword">\begin</span>{alltt}
int mp_prime_is_prime (mp_int * a, int t, int *result)
<span class="enscript-keyword">\end</span>{alltt}
This will perform a trial division followed by <span class="enscript-variable-name">$t$</span> rounds of Miller-Rabin tests on <span class="enscript-variable-name">$a$</span> and store the result in <span class="enscript-variable-name">$result$</span>.  
If <span class="enscript-variable-name">$a$</span> passes all of the tests <span class="enscript-variable-name">$result$</span> is set to one, otherwise it is set to zero.  Note that <span class="enscript-variable-name">$t$</span> is bounded by 
<span class="enscript-variable-name">$1 \le t &lt; PRIME\_SIZE$</span> where <span class="enscript-variable-name">$PRIME\_SIZE$</span> is the number of primes in the prime number table (by default this is <span class="enscript-variable-name">$256$</span>).

<span class="enscript-keyword">\section</span>{Next Prime}
<span class="enscript-keyword">\index</span>{mp<span class="enscript-keyword">\_</span>prime<span class="enscript-keyword">\_</span>next<span class="enscript-keyword">\_</span>prime}
<span class="enscript-keyword">\begin</span>{alltt}
int mp_prime_next_prime(mp_int *a, int t, int bbs_style)
<span class="enscript-keyword">\end</span>{alltt}
This finds the next prime after <span class="enscript-variable-name">$a$</span> that passes mp<span class="enscript-keyword">\_</span>prime<span class="enscript-keyword">\_</span>is<span class="enscript-keyword">\_</span>prime() with <span class="enscript-variable-name">$t$</span> tests.  Set <span class="enscript-variable-name">$bbs\_style$</span> to one if you 
want only the next prime congruent to <span class="enscript-variable-name">$3 \mbox{ mod } 4$</span>, otherwise set it to zero to find any next prime.  

<span class="enscript-keyword">\section</span>{Random Primes}
<span class="enscript-keyword">\index</span>{mp<span class="enscript-keyword">\_</span>prime<span class="enscript-keyword">\_</span>random}
<span class="enscript-keyword">\begin</span>{alltt}
int mp_prime_random(mp_int *a, int t, int size, int bbs, 
                    ltm_prime_callback cb, void *dat)
<span class="enscript-keyword">\end</span>{alltt}
This will find a prime greater than <span class="enscript-variable-name">$256^{size}$</span> which can be ``bbs<span class="enscript-keyword">\_</span>style'' or not depending on <span class="enscript-variable-name">$bbs$</span> and must pass
<span class="enscript-variable-name">$t$</span> rounds of tests.  The ``ltm<span class="enscript-keyword">\_</span>prime<span class="enscript-keyword">\_</span>callback'' is a typedef for 

<span class="enscript-keyword">\begin</span>{alltt}
typedef int ltm_prime_callback(unsigned char *dst, int len, void *dat);
<span class="enscript-keyword">\end</span>{alltt}

Which is a function that must read <span class="enscript-variable-name">$len$</span> bytes (and return the amount stored) into <span class="enscript-variable-name">$dst$</span>.  The <span class="enscript-variable-name">$dat$</span> variable is simply
copied from the original input.  It can be used to pass RNG context data to the callback.  The function 
mp<span class="enscript-keyword">\_</span>prime<span class="enscript-keyword">\_</span>random() is more suitable for generating primes which must be secret (as in the case of RSA) since there 
is no skew on the least significant bits.

<span class="enscript-keyword">\textit</span>{Note:}  As of v0.30 of the LibTomMath library this function has been deprecated.  It is still available
but users are encouraged to use the new mp<span class="enscript-keyword">\_</span>prime<span class="enscript-keyword">\_</span>random<span class="enscript-keyword">\_</span>ex() function instead.

<span class="enscript-keyword">\subsection</span>{Extended Generation}
<span class="enscript-keyword">\index</span>{mp<span class="enscript-keyword">\_</span>prime<span class="enscript-keyword">\_</span>random<span class="enscript-keyword">\_</span>ex}
<span class="enscript-keyword">\begin</span>{alltt}
int mp_prime_random_ex(mp_int *a,    int t, 
                       int     size, int flags, 
                       ltm_prime_callback cb, void *dat);
<span class="enscript-keyword">\end</span>{alltt}
This will generate a prime in <span class="enscript-variable-name">$a$</span> using <span class="enscript-variable-name">$t$</span> tests of the primality testing algorithms.  The variable <span class="enscript-variable-name">$size$</span>
specifies the bit length of the prime desired.  The variable <span class="enscript-variable-name">$flags$</span> specifies one of several options available
(see fig. <span class="enscript-keyword">\ref</span>{fig:primeopts}) which can be OR'ed together.  The callback parameters are used as in 
mp<span class="enscript-keyword">\_</span>prime<span class="enscript-keyword">\_</span>random().

<span class="enscript-keyword">\begin</span>{figure}[here]
<span class="enscript-keyword">\begin</span>{center}
<span class="enscript-keyword">\begin</span>{small}
<span class="enscript-keyword">\begin</span>{tabular}{|r|l|}
<span class="enscript-keyword">\hline</span> <span class="enscript-keyword">\textbf</span>{Flag}         &amp; <span class="enscript-keyword">\textbf</span>{Meaning} <span class="enscript-keyword">\\</span>
<span class="enscript-keyword">\hline</span> LTM<span class="enscript-keyword">\_</span>PRIME<span class="enscript-keyword">\_</span>BBS       &amp; Make the prime congruent to <span class="enscript-variable-name">$3$</span> modulo <span class="enscript-variable-name">$4$</span> <span class="enscript-keyword">\\</span>
<span class="enscript-keyword">\hline</span> LTM<span class="enscript-keyword">\_</span>PRIME<span class="enscript-keyword">\_</span>SAFE      &amp; Make a prime <span class="enscript-variable-name">$p$</span> such that <span class="enscript-variable-name">$(p - 1)/2$</span> is also prime. <span class="enscript-keyword">\\</span>
                             &amp; This option implies LTM<span class="enscript-keyword">\_</span>PRIME<span class="enscript-keyword">\_</span>BBS as well. <span class="enscript-keyword">\\</span>
<span class="enscript-keyword">\hline</span> LTM<span class="enscript-keyword">\_</span>PRIME<span class="enscript-keyword">\_</span>2MSB<span class="enscript-keyword">\_</span>OFF &amp; Makes sure that the bit adjacent to the most significant bit <span class="enscript-keyword">\\</span>
                             &amp; Is forced to zero.  <span class="enscript-keyword">\\</span>
<span class="enscript-keyword">\hline</span> LTM<span class="enscript-keyword">\_</span>PRIME<span class="enscript-keyword">\_</span>2MSB<span class="enscript-keyword">\_</span>ON  &amp; Makes sure that the bit adjacent to the most significant bit <span class="enscript-keyword">\\</span>
                             &amp; Is forced to one. <span class="enscript-keyword">\\</span>
<span class="enscript-keyword">\hline</span>
<span class="enscript-keyword">\end</span>{tabular}
<span class="enscript-keyword">\end</span>{small}
<span class="enscript-keyword">\end</span>{center}
<span class="enscript-keyword">\caption</span>{Primality Generation Options}
<span class="enscript-keyword">\label</span>{fig:primeopts}
<span class="enscript-keyword">\end</span>{figure}

<span class="enscript-keyword">\chapter</span>{Input and Output}
<span class="enscript-keyword">\section</span>{ASCII Conversions}
<span class="enscript-keyword">\subsection</span>{To ASCII}
<span class="enscript-keyword">\index</span>{mp<span class="enscript-keyword">\_</span>toradix}
<span class="enscript-keyword">\begin</span>{alltt}
int mp_toradix (mp_int * a, char *str, int radix);
<span class="enscript-keyword">\end</span>{alltt}
This still store <span class="enscript-variable-name">$a$</span> in ``str'' as a base-``radix'' string of ASCII chars.  This function appends a NUL character
to terminate the string.  Valid values of ``radix'' line in the range <span class="enscript-variable-name">$[2, 64]$</span>.  To determine the size (exact) required
by the conversion before storing any data use the following function.

<span class="enscript-keyword">\index</span>{mp<span class="enscript-keyword">\_</span>radix<span class="enscript-keyword">\_</span>size}
<span class="enscript-keyword">\begin</span>{alltt}
int mp_radix_size (mp_int * a, int radix, int *size)
<span class="enscript-keyword">\end</span>{alltt}
This stores in ``size'' the number of characters (including space for the NUL terminator) required.  Upon error this 
function returns an error code and ``size'' will be zero.  

<span class="enscript-keyword">\subsection</span>{From ASCII}
<span class="enscript-keyword">\index</span>{mp<span class="enscript-keyword">\_</span>read<span class="enscript-keyword">\_</span>radix}
<span class="enscript-keyword">\begin</span>{alltt}
int mp_read_radix (mp_int * a, char *str, int radix);
<span class="enscript-keyword">\end</span>{alltt}
This will read the base-``radix'' NUL terminated string from ``str'' into <span class="enscript-variable-name">$a$</span>.  It will stop reading when it reads a
character it does not recognize (which happens to include th NUL char... imagine that...).  A single leading <span class="enscript-variable-name">$-$</span> sign
can be used to denote a negative number.

<span class="enscript-keyword">\section</span>{Binary Conversions}

Converting an mp<span class="enscript-keyword">\_</span>int to and from binary is another keen idea.

<span class="enscript-keyword">\index</span>{mp<span class="enscript-keyword">\_</span>unsigned<span class="enscript-keyword">\_</span>bin<span class="enscript-keyword">\_</span>size}
<span class="enscript-keyword">\begin</span>{alltt}
int mp_unsigned_bin_size(mp_int *a);
<span class="enscript-keyword">\end</span>{alltt}

This will return the number of bytes (octets) required to store the unsigned copy of the integer <span class="enscript-variable-name">$a$</span>.

<span class="enscript-keyword">\index</span>{mp<span class="enscript-keyword">\_</span>to<span class="enscript-keyword">\_</span>unsigned<span class="enscript-keyword">\_</span>bin}
<span class="enscript-keyword">\begin</span>{alltt}
int mp_to_unsigned_bin(mp_int *a, unsigned char *b);
<span class="enscript-keyword">\end</span>{alltt}
This will store <span class="enscript-variable-name">$a$</span> into the buffer <span class="enscript-variable-name">$b$</span> in big--endian format.  Fortunately this is exactly what DER (or is it ASN?)
requires.  It does not store the sign of the integer.

<span class="enscript-keyword">\index</span>{mp<span class="enscript-keyword">\_</span>read<span class="enscript-keyword">\_</span>unsigned<span class="enscript-keyword">\_</span>bin}
<span class="enscript-keyword">\begin</span>{alltt}
int mp_read_unsigned_bin(mp_int *a, unsigned char *b, int c);
<span class="enscript-keyword">\end</span>{alltt}
This will read in an unsigned big--endian array of bytes (octets) from <span class="enscript-variable-name">$b$</span> of length <span class="enscript-variable-name">$c$</span> into <span class="enscript-variable-name">$a$</span>.  The resulting
integer <span class="enscript-variable-name">$a$</span> will always be positive.

For those who acknowledge the existence of negative numbers (heretic!) there are ``signed'' versions of the
previous functions.

<span class="enscript-keyword">\begin</span>{alltt}
int mp_signed_bin_size(mp_int *a);
int mp_read_signed_bin(mp_int *a, unsigned char *b, int c);
int mp_to_signed_bin(mp_int *a, unsigned char *b);
<span class="enscript-keyword">\end</span>{alltt}
They operate essentially the same as the unsigned copies except they prefix the data with zero or non--zero
byte depending on the sign.  If the sign is zpos (e.g. not negative) the prefix is zero, otherwise the prefix
is non--zero.  

<span class="enscript-keyword">\chapter</span>{Algebraic Functions}
<span class="enscript-keyword">\section</span>{Extended Euclidean Algorithm}
<span class="enscript-keyword">\index</span>{mp<span class="enscript-keyword">\_</span>exteuclid}
<span class="enscript-keyword">\begin</span>{alltt}
int mp_exteuclid(mp_int *a, mp_int *b, 
                 mp_int *U1, mp_int *U2, mp_int *U3);
<span class="enscript-keyword">\end</span>{alltt}

This finds the triple U1/U2/U3 using the Extended Euclidean algorithm such that the following equation holds.

<span class="enscript-keyword">\begin</span>{equation}
a <span class="enscript-keyword">\cdot</span> U1 + b <span class="enscript-keyword">\cdot</span> U2 = U3
<span class="enscript-keyword">\end</span>{equation}

Any of the U1/U2/U3 paramters can be set to <span class="enscript-keyword">\textbf</span>{NULL} if they are not desired.  

<span class="enscript-keyword">\section</span>{Greatest Common Divisor}
<span class="enscript-keyword">\index</span>{mp<span class="enscript-keyword">\_</span>gcd}
<span class="enscript-keyword">\begin</span>{alltt}
int mp_gcd (mp_int * a, mp_int * b, mp_int * c)
<span class="enscript-keyword">\end</span>{alltt}
This will compute the greatest common divisor of <span class="enscript-variable-name">$a$</span> and <span class="enscript-variable-name">$b$</span> and store it in <span class="enscript-variable-name">$c$</span>.

<span class="enscript-keyword">\section</span>{Least Common Multiple}
<span class="enscript-keyword">\index</span>{mp<span class="enscript-keyword">\_</span>lcm}
<span class="enscript-keyword">\begin</span>{alltt}
int mp_lcm (mp_int * a, mp_int * b, mp_int * c)
<span class="enscript-keyword">\end</span>{alltt}
This will compute the least common multiple of <span class="enscript-variable-name">$a$</span> and <span class="enscript-variable-name">$b$</span> and store it in <span class="enscript-variable-name">$c$</span>.

<span class="enscript-keyword">\section</span>{Jacobi Symbol}
<span class="enscript-keyword">\index</span>{mp<span class="enscript-keyword">\_</span>jacobi}
<span class="enscript-keyword">\begin</span>{alltt}
int mp_jacobi (mp_int * a, mp_int * p, int *c)
<span class="enscript-keyword">\end</span>{alltt}
This will compute the Jacobi symbol for <span class="enscript-variable-name">$a$</span> with respect to <span class="enscript-variable-name">$p$</span>.  If <span class="enscript-variable-name">$p$</span> is prime this essentially computes the Legendre
symbol.  The result is stored in <span class="enscript-variable-name">$c$</span> and can take on one of three values <span class="enscript-variable-name">$\lbrace -1, 0, 1 \rbrace$</span>.  If <span class="enscript-variable-name">$p$</span> is prime
then the result will be <span class="enscript-variable-name">$-1$</span> when <span class="enscript-variable-name">$a$</span> is not a quadratic residue modulo <span class="enscript-variable-name">$p$</span>.  The result will be <span class="enscript-variable-name">$0$</span> if <span class="enscript-variable-name">$a$</span> divides <span class="enscript-variable-name">$p$</span>
and the result will be <span class="enscript-variable-name">$1$</span> if <span class="enscript-variable-name">$a$</span> is a quadratic residue modulo <span class="enscript-variable-name">$p$</span>.  

<span class="enscript-keyword">\section</span>{Modular Inverse}
<span class="enscript-keyword">\index</span>{mp<span class="enscript-keyword">\_</span>invmod}
<span class="enscript-keyword">\begin</span>{alltt}
int mp_invmod (mp_int * a, mp_int * b, mp_int * c)
<span class="enscript-keyword">\end</span>{alltt}
Computes the multiplicative inverse of <span class="enscript-variable-name">$a$</span> modulo <span class="enscript-variable-name">$b$</span> and stores the result in <span class="enscript-variable-name">$c$</span> such that <span class="enscript-variable-name">$ac \equiv 1 \mbox{ (mod }b\mbox{)}$</span>.

<span class="enscript-keyword">\section</span>{Single Digit Functions}

For those using small numbers (<span class="enscript-keyword">\textit</span>{snicker snicker}) there are several ``helper'' functions

<span class="enscript-keyword">\index</span>{mp<span class="enscript-keyword">\_</span>add<span class="enscript-keyword">\_</span>d} <span class="enscript-keyword">\index</span>{mp<span class="enscript-keyword">\_</span>sub<span class="enscript-keyword">\_</span>d} <span class="enscript-keyword">\index</span>{mp<span class="enscript-keyword">\_</span>mul<span class="enscript-keyword">\_</span>d} <span class="enscript-keyword">\index</span>{mp<span class="enscript-keyword">\_</span>div<span class="enscript-keyword">\_</span>d} <span class="enscript-keyword">\index</span>{mp<span class="enscript-keyword">\_</span>mod<span class="enscript-keyword">\_</span>d}
<span class="enscript-keyword">\begin</span>{alltt}
int mp_add_d(mp_int *a, mp_digit b, mp_int *c);
int mp_sub_d(mp_int *a, mp_digit b, mp_int *c);
int mp_mul_d(mp_int *a, mp_digit b, mp_int *c);
int mp_div_d(mp_int *a, mp_digit b, mp_int *c, mp_digit *d);
int mp_mod_d(mp_int *a, mp_digit b, mp_digit *c);
<span class="enscript-keyword">\end</span>{alltt}

These work like the full mp<span class="enscript-keyword">\_</span>int capable variants except the second parameter <span class="enscript-variable-name">$b$</span> is a mp<span class="enscript-keyword">\_</span>digit.  These
functions fairly handy if you have to work with relatively small numbers since you will not have to allocate
an entire mp<span class="enscript-keyword">\_</span>int to store a number like <span class="enscript-variable-name">$1$</span> or <span class="enscript-variable-name">$2$</span>.

<span class="enscript-keyword">\input</span>{bn.ind}

<span class="enscript-keyword">\end</span>{document}
</pre>
<hr />
</body></html>