bn.tex

tommath库

      printf("Error setting the value of the number.  \%s", 
             mp_error_to_string(result));
      return EXIT_FAILURE;
   \}

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

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

   return EXIT_SUCCESS;
\}
\end{alltt} \end{small}

This should output the following if the program succeeds.

\begin{alltt}
number == 654321
\end{alltt}

\subsection{Initialize and Setting Constants}
To both initialize and set small constants the following two functions are available.
\index{mp\_init\_set} \index{mp\_init\_set\_int}
\begin{alltt}
int mp_init_set (mp_int * a, mp_digit b);
int mp_init_set_int (mp_int * a, unsigned long b);
\end{alltt}

Both functions work like the previous counterparts except they first mp\_init $a$ before setting the values.  

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

   /* initialize and set a single digit */
   if ((result = mp_init_set(&number1, 100)) != MP_OKAY) \{
      printf("Error setting number1: \%s", 
             mp_error_to_string(result));
      return EXIT_FAILURE;
   \}             

   /* initialize and set a long */
   if ((result = mp_init_set_int(&number2, 1023)) != MP_OKAY) \{
      printf("Error setting number2: \%s", 
             mp_error_to_string(result));
      return EXIT_FAILURE;
   \}

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

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

   return EXIT_SUCCESS;
\}
\end{alltt}

If this program succeeds it shall output.
\begin{alltt}
Number1, Number2 == 100, 1023
\end{alltt}

\section{Comparisons}

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

\index{MP\_GT} \index{MP\_EQ} \index{MP\_LT}
\begin{figure}[here]
\begin{center}
\begin{tabular}{|c|c|}
\hline \textbf{Result Code} & \textbf{Meaning} \\
\hline MP\_GT & $a > b$ \\
\hline MP\_EQ & $a = b$ \\
\hline MP\_LT & $a < b$ \\
\hline
\end{tabular}
\end{center}
\caption{Comparison Codes for $a, b$}
\label{fig:CMP}
\end{figure}

In figure \ref{fig:CMP} two integers $a$ and $b$ are being compared.  In this case $a$ is said to be ``to the left'' of 
$b$.  

\subsection{Unsigned comparison}

An unsigned comparison considers only the digits themselves and not the associated \textit{sign} flag of the 
mp\_int structures.  This is analogous to an absolute comparison.  The function mp\_cmp\_mag() will compare two
mp\_int variables based on their digits only. 

\index{mp\_cmp\_mag}
\begin{alltt}
int mp_cmp(mp_int * a, mp_int * b);
\end{alltt}
This will compare $a$ to $b$ placing $a$ to the left of $b$.  This function cannot fail and will return one of the
three compare codes listed in figure \ref{fig:CMP}.

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

   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 number1 to 5 */
   mp_set(&number1, 5);
  
   /* set the number2 to -6 */
   mp_set(&number2, 6);
   if ((result = mp_neg(&number2, &number2)) != MP_OKAY) \{
      printf("Error negating number2.  \%s", 
             mp_error_to_string(result));
      return EXIT_FAILURE;
   \}

   switch(mp_cmp_mag(&number1, &number2)) \{
       case MP_GT:  printf("|number1| > |number2|"); break;
       case MP_EQ:  printf("|number1| = |number2|"); break;
       case MP_LT:  printf("|number1| < |number2|"); break;
   \}

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

   return EXIT_SUCCESS;
\}
\end{alltt} \end{small}

If this program\footnote{This function uses the mp\_neg() function which is discussed in section \ref{sec:NEG}.} completes 
successfully it should print the following.

\begin{alltt}
|number1| < |number2|
\end{alltt}

This is because $\vert -6 \vert = 6$ and obviously $5 < 6$.

\subsection{Signed comparison}

To compare two mp\_int variables based on their signed value the mp\_cmp() function is provided.

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

This will compare $a$ to the left of $b$.  It will first compare the signs of the two mp\_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 \ref{fig:CMP}.

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

   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 number1 to 5 */
   mp_set(&number1, 5);
  
   /* set the number2 to -6 */
   mp_set(&number2, 6);
   if ((result = mp_neg(&number2, &number2)) != MP_OKAY) \{
      printf("Error negating number2.  \%s", 
             mp_error_to_string(result));
      return EXIT_FAILURE;
   \}

   switch(mp_cmp(&number1, &number2)) \{
       case MP_GT:  printf("number1 > number2"); break;
       case MP_EQ:  printf("number1 = number2"); break;
       case MP_LT:  printf("number1 < number2"); break;
   \}

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

   return EXIT_SUCCESS;
\}
\end{alltt} \end{small}

If this program\footnote{This function uses the mp\_neg() function which is discussed in section \ref{sec:NEG}.} completes 
successfully it should print the following.

\begin{alltt}
number1 > number2
\end{alltt}

\subsection{Single Digit}

To compare a single digit against an mp\_int the following function has been provided.

\index{mp\_cmp\_d}
\begin{alltt}
int mp_cmp_d(mp_int * a, mp_digit b);
\end{alltt}

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


\begin{small} \begin{alltt}
int main(void)
\{
   mp_int number;
   int result;

   if ((result = mp_init(&number)) != MP_OKAY) \{
      printf("Error initializing the number.  \%s", 
             mp_error_to_string(result));
      return EXIT_FAILURE;
   \}
 
   /* set the number to 5 */
   mp_set(&number, 5);

   switch(mp_cmp_d(&number, 7)) \{
       case MP_GT:  printf("number > 7"); break;
       case MP_EQ:  printf("number = 7"); break;
       case MP_LT:  printf("number < 7"); break;
   \}

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

   return EXIT_SUCCESS;
\}
\end{alltt} \end{small}

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

\begin{alltt}
number < 7
\end{alltt}

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

\subsection{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.
\index{mp\_mul\_2} \index{mp\_div\_2}
\begin{alltt}
int mp_mul_2(mp_int * a, mp_int * b);
int mp_div_2(mp_int * a, mp_int * b);
\end{alltt}

The former will assign twice $a$ to $b$ while the latter will assign half $a$ to $b$.  These functions are fast
since the shift counts and maskes are hardcoded into the routines.

\begin{small} \begin{alltt}
int main(void)
\{
   mp_int number;
   int result;

   if ((result = mp_init(&number)) != MP_OKAY) \{
      printf("Error initializing the number.  \%s", 
             mp_error_to_string(result));
      return EXIT_FAILURE;
   \}
 
   /* set the number to 5 */
   mp_set(&number, 5);

   /* multiply by two */
   if ((result = mp\_mul\_2(&number, &number)) != MP_OKAY) \{
      printf("Error multiplying the number.  \%s", 
             mp_error_to_string(result));
      return EXIT_FAILURE;
   \}
   switch(mp_cmp_d(&number, 7)) \{
       case MP_GT:  printf("2*number > 7"); break;
       case MP_EQ:  printf("2*number = 7"); break;
       case MP_LT:  printf("2*number < 7"); break;
   \}

   /* now divide by two */
   if ((result = mp\_div\_2(&number, &number)) != MP_OKAY) \{
      printf("Error dividing the number.  \%s", 
             mp_error_to_string(result));
      return EXIT_FAILURE;
   \}
   switch(mp_cmp_d(&number, 7)) \{
       case MP_GT:  printf("2*number/2 > 7"); break;
       case MP_EQ:  printf("2*number/2 = 7"); break;
       case MP_LT:  printf("2*number/2 < 7"); break;
   \}

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

   return EXIT_SUCCESS;
\}
\end{alltt} \end{small}

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

\begin{alltt}
2*number > 7
2*number/2 < 7
\end{alltt}

Since $10 > 7$ and $5 < 7$.  To multiply by a power of two the following function can be used.

\index{mp\_mul\_2d}
\begin{alltt}
int mp_mul_2d(mp_int * a, int b, mp_int * c);
\end{alltt}

This will multiply $a$ by $2^b$ and store the result in ``c''.  If the value of $b$ is less than or equal to 
zero the function will copy $a$ to ``c'' without performing any further actions.  

To divide by a power of two use the following.

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

\subsection{Polynomial Basis Operations}

Strictly speaking the organization of the integers within the mp\_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
$f(x) = \sum_{i=0}^{k} y_ix^k$ for any vector $\vec y$ then the array of digits in $\vec y$ are said to be 
the polynomial basis representation of $z$ if $f(\beta) = z$ for a given radix $\beta$.  

To multiply by the polynomial $g(x) = x$ all you have todo is shift the digits of the basis left one place.  The
following function provides this operation.

\index{mp\_lshd}
\begin{alltt}