bn.tex

tommath库

int mp_lshd (mp_int * a, int b);
\end{alltt}

This will multiply $a$ in place by $x^b$ which is equivalent to shifting the digits left $b$ places and inserting zeroes
in the least significant digits.  Similarly to divide by a power of $x$ the following function is provided.

\index{mp\_rshd}
\begin{alltt}
void mp_rshd (mp_int * a, int b)
\end{alltt}
This will divide $a$ in place by $x^b$ and discard the remainder.  This function cannot fail as it performs the operations
in place and no new digits are required to complete it.

\subsection{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.

\index{mp\_or} \index{mp\_and} \index{mp\_xor}
\begin{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);
\end{alltt}

Which compute $c = a \odot b$ where $\odot$ is one of OR, AND or XOR.  

\section{Addition and Subtraction}

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

\index{mp\_add} \index{mp\_sub}
\begin{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)
\end{alltt}

Which perform $c = a \odot b$ where $\odot$ is one of signed addition or subtraction.  The operations are fully sign
aware.

\section{Sign Manipulation}
\subsection{Negation}
\label{sec:NEG}
Simple integer negation can be performed with the following.

\index{mp\_neg}
\begin{alltt}
int mp_neg (mp_int * a, mp_int * b);
\end{alltt}

Which assigns $-a$ to $b$.  

\subsection{Absolute}
Simple integer absolutes can be performed with the following.

\index{mp\_neg}
\begin{alltt}
int mp_abs (mp_int * a, mp_int * b);
\end{alltt}

Which assigns $\vert a \vert$ to $b$.  

\section{Integer Division and Remainder}
To perform a complete and general integer division with remainder use the following function.

\index{mp\_div}
\begin{alltt}
int mp_div (mp_int * a, mp_int * b, mp_int * c, mp_int * d);
\end{alltt}
                                                        
This divides $a$ by $b$ and stores the quotient in $c$ and $d$.  The signed quotient is computed such that 
$bc + d = a$.  Note that either of $c$ or $d$ can be set to \textbf{NULL} if their value is not required.  If 
$b$ is zero the function returns \textbf{MP\_VAL}.  


\chapter{Multiplication and Squaring}
\section{Multiplication}
A full signed integer multiplication can be performed with the following.
\index{mp\_mul}
\begin{alltt}
int mp_mul (mp_int * a, mp_int * b, mp_int * c);
\end{alltt}
Which assigns the full signed product $ab$ to $c$.  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\_mul()
will determine on its own\footnote{Some tweaking may be required.} what routine to use automatically when it is called.

\begin{alltt}
int main(void)
\{
   mp_int number1, number2;
   int result;

   /* Initialize the numbers */
   if ((result = mp_init_multi(&number1, 
                               &number2, NULL)) != MP_OKAY) \{
      printf("Error initializing the numbers.  \%s", 
             mp_error_to_string(result));
      return EXIT_FAILURE;
   \}

   /* set the terms */
   if ((result = mp_set_int(&number, 257)) != MP_OKAY) \{
      printf("Error setting number1.  \%s", 
             mp_error_to_string(result));
      return EXIT_FAILURE;
   \}
 
   if ((result = mp_set_int(&number2, 1023)) != MP_OKAY) \{
      printf("Error setting number2.  \%s", 
             mp_error_to_string(result));
      return EXIT_FAILURE;
   \}

   /* multiply them */
   if ((result = mp_mul(&number1, &number2,
                        &number1)) != MP_OKAY) \{
      printf("Error multiplying terms.  \%s", 
             mp_error_to_string(result));
      return EXIT_FAILURE;
   \}

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

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

   return EXIT_SUCCESS;
\}
\end{alltt}   

If this program succeeds it shall output the following.

\begin{alltt}
number1 * number2 == 262911
\end{alltt}

\section{Squaring}
Since squaring can be performed faster than multiplication it is performed it's own function instead of just using
mp\_mul().

\index{mp\_sqr}
\begin{alltt}
int mp_sqr (mp_int * a, mp_int * b);
\end{alltt}

Will square $a$ and store it in $b$.  Like the case of multiplication there are four different squaring
algorithms all which can be called from mp\_sqr().  It is ideal to use mp\_sqr over mp\_mul when squaring terms.

\section{Tuning Polynomial Basis Routines}

Both of the Toom-Cook and Karatsuba multiplication algorithms are faster than the traditional $O(n^2)$ approach that
the Comba and baseline algorithms use.  At $O(n^{1.464973})$ and $O(n^{1.584962})$ running times respectfully 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

\begin{alltt}
make XXX
\end{alltt}
Where ``XXX'' is one of the following entries from the table \ref{fig:tuning}.

\begin{figure}[here]
\begin{center}
\begin{small}
\begin{tabular}{|l|l|}
\hline \textbf{Value of XXX} & \textbf{Meaning} \\
\hline tune & Builds portable tuning application \\
\hline tune86 & Builds x86 (pentium and up) program for COFF \\
\hline tune86c & Builds x86 program for Cygwin \\
\hline tune86l & Builds x86 program for Linux (ELF format) \\
\hline
\end{tabular}
\end{small}
\end{center}
\caption{Build Names for Tuning Programs}
\label{fig:tuning}
\end{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.

\chapter{Modular Reduction}

Modular reduction is process of taking the remainder of one quantity divided by another.  Expressed 
as (\ref{eqn:mod}) the modular reduction is equivalent to the remainder of $b$ divided by $c$.  

\begin{equation}
a \equiv b \mbox{ (mod }c\mbox{)}
\label{eqn:mod}
\end{equation}

Of particular interest to cryptography are reductions where $b$ is limited to the range $0 \le b < c^2$ 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\_exptmod when an appropriate modulus is detected.  

\section{Straight Division}
In order to effect an arbitrary modular reduction the following algorithm is provided.

\index{mp\_mod}
\begin{alltt}
int mp_mod(mp_int *a, mp_int *b, mp_int *c);
\end{alltt}

This reduces $a$ modulo $b$ and stores the result in $c$.  The sign of $c$ shall agree with the sign 
of $b$.  This algorithm accepts an input $a$ of any range and is not limited by $0 \le a < b^2$.

\section{Barrett Reduction}

Barrett reduction is a generic optimized reduction algorithm that requires pre--computation to achieve
a decent speedup over straight division.  First a $mu$ value must be precomputed with the following function.

\index{mp\_reduce\_setup}
\begin{alltt}
int mp_reduce_setup(mp_int *a, mp_int *b);
\end{alltt}

Given a modulus in $b$ this produces the required $mu$ value in $a$.  For any given modulus this only has to
be computed once.  Modular reduction can now be performed with the following.

\index{mp\_reduce}
\begin{alltt}
int mp_reduce(mp_int *a, mp_int *b, mp_int *c);
\end{alltt}

This will reduce $a$ in place modulo $b$ with the precomputed $mu$ value in $c$.  $a$ must be in the range
$0 \le a < b^2$.

\begin{alltt}
int main(void)
\{
   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(&mu, b)) != MP_OKAY) \{
      printf("Error getting mu.  \%s", 
             mp_error_to_string(result));
      return EXIT_FAILURE;
   \}

   /* square a to get c = a^2 */
   if ((result = mp_sqr(&a, &c)) != MP_OKAY) \{
      printf("Error squaring.  \%s", 
             mp_error_to_string(result));
      return EXIT_FAILURE;
   \}

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

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

   return EXIT_SUCCESS;
\}
\end{alltt} 

This program will calculate $a^3 \mbox{ mod }b$ if all the functions succeed.  

\section{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.

\index{mp\_montgomery\_setup}
\begin{alltt}
int mp_montgomery_setup(mp_int *a, mp_digit *mp);
\end{alltt}

For the given odd moduli $a$ the precomputation value is placed in $mp$.  The reduction is computed with the 
following.

\index{mp\_montgomery\_reduce}
\begin{alltt}
int mp_montgomery_reduce(mp_int *a, mp_int *m, mp_digit mp);
\end{alltt}
This reduces $a$ in place modulo $m$ with the pre--computed value $mp$.   $a$ must be in the range
$0 \le a < b^2$.

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

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

To quickly calculate $R$ the following function was provided.

\index{mp\_montgomery\_calc\_normalization}
\begin{alltt}
int mp_montgomery_calc_normalization(mp_int *a, mp_int *b);
\end{alltt}
Which calculates $a = R$ for the odd moduli $b$ 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 $a^3 \mbox { mod }b$ using Montgomery reduction the value of $a$ can be normalized by
multiplying it by $R$.  Consider the following code snippet.

\begin{alltt}
int main(void)
\{
   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(&R, b)) != MP_OKAY) \{
      printf("Error getting norm.  \%s", 
             mp_error_to_string(result));
      return EXIT_FAILURE;
   \}

   /* get mp value */