tommath.tex

tommath库

\hline $\left [ 4 \right ]$ & A moderately hard problem that involves a non-trivial amount \\
                     & of work and research, the solution to which will demonstrate \\
                     & a higher mastery of the subject matter. \\
\hline $\left [ 5 \right ]$ & A hard problem that involves concepts that are difficult for a \\
                     & novice to solve.  Solutions to these problems will demonstrate a \\
                     & complete mastery of the given subject. \\
\hline
\end{tabular}
\end{small}
\end{center}
\caption{Exercise Scoring System}
\end{figure}

Problems at the first level are meant to be simple questions that the reader can answer quickly without programming a solution or
devising new theory.  These problems are quick tests to see if the material is understood.  Problems at the second level 
are also designed to be easy but will require a program or algorithm to be implemented to arrive at the answer.  These
two levels are essentially entry level questions.  

Problems at the third level are meant to be a bit more difficult than the first two levels.  The answer is often 
fairly obvious but arriving at an exacting solution requires some thought and skill.  These problems will almost always 
involve devising a new algorithm or implementing a variation of another algorithm previously presented.  Readers who can
answer these questions will feel comfortable with the concepts behind the topic at hand.

Problems at the fourth level are meant to be similar to those of the level three questions except they will require 
additional research to be completed.  The reader will most likely not know the answer right away, nor will the text provide 
the exact details of the answer until a subsequent chapter.  

Problems at the fifth level are meant to be the hardest 
problems relative to all the other problems in the chapter.  People who can correctly answer fifth level problems have a 
mastery of the subject matter at hand.

Often problems will be tied together.  The purpose of this is to start a chain of thought that will be discussed in future chapters.  The reader
is encouraged to answer the follow-up problems and try to draw the relevance of problems.

\section{Introduction to LibTomMath}

\subsection{What is LibTomMath?}
LibTomMath is a free and open source multiple precision integer library written entirely in portable ISO C.  By portable it 
is meant that the library does not contain any code that is computer platform dependent or otherwise problematic to use on 
any given platform.  

The library has been successfully tested under numerous operating systems including Unix\footnote{All of these
trademarks belong to their respective rightful owners.}, MacOS, Windows, Linux, PalmOS and on standalone hardware such 
as the Gameboy Advance.  The library is designed to contain enough functionality to be able to develop applications such 
as public key cryptosystems and still maintain a relatively small footprint.

\subsection{Goals of LibTomMath}

Libraries which obtain the most efficiency are rarely written in a high level programming language such as C.  However, 
even though this library is written entirely in ISO C, considerable care has been taken to optimize the algorithm implementations within the 
library.  Specifically the code has been written to work well with the GNU C Compiler (\textit{GCC}) on both x86 and ARM 
processors.  Wherever possible, highly efficient algorithms, such as Karatsuba multiplication, sliding window 
exponentiation and Montgomery reduction have been provided to make the library more efficient.  

Even with the nearly optimal and specialized algorithms that have been included the Application Programing Interface 
(\textit{API}) has been kept as simple as possible.  Often generic place holder routines will make use of specialized 
algorithms automatically without the developer's specific attention.  One such example is the generic multiplication 
algorithm \textbf{mp\_mul()} which will automatically use Toom--Cook, Karatsuba, Comba or baseline multiplication 
based on the magnitude of the inputs and the configuration of the library.  

Making LibTomMath as efficient as possible is not the only goal of the LibTomMath project.  Ideally the library should 
be source compatible with another popular library which makes it more attractive for developers to use.  In this case the
MPI library was used as a API template for all the basic functions.  MPI was chosen because it is another library that fits 
in the same niche as LibTomMath.  Even though LibTomMath uses MPI as the template for the function names and argument 
passing conventions, it has been written from scratch by Tom St Denis.

The project is also meant to act as a learning tool for students, the logic being that no easy-to-follow ``bignum'' 
library exists which can be used to teach computer science students how to perform fast and reliable multiple precision 
integer arithmetic.  To this end the source code has been given quite a few comments and algorithm discussion points.  

\section{Choice of LibTomMath}
LibTomMath was chosen as the case study of this text not only because the author of both projects is one and the same but
for more worthy reasons.  Other libraries such as GMP \cite{GMP}, MPI \cite{MPI}, LIP \cite{LIP} and OpenSSL 
\cite{OPENSSL} have multiple precision integer arithmetic routines but would not be ideal for this text for 
reasons that will be explained in the following sub-sections.

\subsection{Code Base}
The LibTomMath code base is all portable ISO C source code.  This means that there are no platform dependent conditional
segments of code littered throughout the source.  This clean and uncluttered approach to the library means that a
developer can more readily discern the true intent of a given section of source code without trying to keep track of
what conditional code will be used.

The code base of LibTomMath is well organized.  Each function is in its own separate source code file 
which allows the reader to find a given function very quickly.  On average there are $76$ lines of code per source
file which makes the source very easily to follow.  By comparison MPI and LIP are single file projects making code tracing
very hard.  GMP has many conditional code segments which also hinder tracing.  

When compiled with GCC for the x86 processor and optimized for speed the entire library is approximately $100$KiB\footnote{The notation ``KiB'' means $2^{10}$ octets, similarly ``MiB'' means $2^{20}$ octets.}
 which is fairly small compared to GMP (over $250$KiB).  LibTomMath is slightly larger than MPI (which compiles to about 
$50$KiB) but LibTomMath is also much faster and more complete than MPI.

\subsection{API Simplicity}
LibTomMath is designed after the MPI library and shares the API design.  Quite often programs that use MPI will build 
with LibTomMath without change. The function names correlate directly to the action they perform.  Almost all of the 
functions share the same parameter passing convention.  The learning curve is fairly shallow with the API provided 
which is an extremely valuable benefit for the student and developer alike.  

The LIP library is an example of a library with an API that is awkward to work with.  LIP uses function names that are often ``compressed'' to 
illegible short hand.  LibTomMath does not share this characteristic.  

The GMP library also does not return error codes.  Instead it uses a POSIX.1 \cite{POSIX1} signal system where errors
are signaled to the host application.  This happens to be the fastest approach but definitely not the most versatile.  In
effect a math error (i.e. invalid input, heap error, etc) can cause a program to stop functioning which is definitely 
undersireable in many situations.

\subsection{Optimizations}
While LibTomMath is certainly not the fastest library (GMP often beats LibTomMath by a factor of two) it does
feature a set of optimal algorithms for tasks such as modular reduction, exponentiation, multiplication and squaring.  GMP 
and LIP also feature such optimizations while MPI only uses baseline algorithms with no optimizations.  GMP lacks a few
of the additional modular reduction optimizations that LibTomMath features\footnote{At the time of this writing GMP
only had Barrett and Montgomery modular reduction algorithms.}.  

LibTomMath is almost always an order of magnitude faster than the MPI library at computationally expensive tasks such as modular
exponentiation.  In the grand scheme of ``bignum'' libraries LibTomMath is faster than the average library and usually  
slower than the best libraries such as GMP and OpenSSL by only a small factor.

\subsection{Portability and Stability}
LibTomMath will build ``out of the box'' on any platform equipped with a modern version of the GNU C Compiler 
(\textit{GCC}).  This means that without changes the library will build without configuration or setting up any 
variables.  LIP and MPI will build ``out of the box'' as well but have numerous known bugs.  Most notably the author of 
MPI has recently stopped working on his library and LIP has long since been discontinued.  

GMP requires a configuration script to run and will not build out of the box.   GMP and LibTomMath are still in active
development and are very stable across a variety of platforms.

\subsection{Choice}
LibTomMath is a relatively compact, well documented, highly optimized and portable library which seems only natural for
the case study of this text.  Various source files from the LibTomMath project will be included within the text.  However, 
the reader is encouraged to download their own copy of the library to actually be able to work with the library.  

\chapter{Getting Started}
\section{Library Basics}
The trick to writing any useful library of source code is to build a solid foundation and work outwards from it.  First, 
a problem along with allowable solution parameters should be identified and analyzed.  In this particular case the 
inability to accomodate multiple precision integers is the problem.  Futhermore, the solution must be written
as portable source code that is reasonably efficient across several different computer platforms.

After a foundation is formed the remainder of the library can be designed and implemented in a hierarchical fashion.  
That is, to implement the lowest level dependencies first and work towards the most abstract functions last.  For example, 
before implementing a modular exponentiation algorithm one would implement a modular reduction algorithm.
By building outwards from a base foundation instead of using a parallel design methodology the resulting project is 
highly modular.  Being highly modular is a desirable property of any project as it often means the resulting product
has a small footprint and updates are easy to perform.  

Usually when I start a project I will begin with the header files.  I define the data types I think I will need and 
prototype the initial functions that are not dependent on other functions (within the library).  After I 
implement these base functions I prototype more dependent functions and implement them.   The process repeats until
I implement all of the functions I require.  For example, in the case of LibTomMath I implemented functions such as 
mp\_init() well before I implemented mp\_mul() and even further before I implemented mp\_exptmod().  As an example as to 
why this design works note that the Karatsuba and Toom-Cook multipliers were written \textit{after} the 
dependent function mp\_exptmod() was written.  Adding the new multiplication algorithms did not require changes to the 
mp\_exptmod() function itself and lowered the total cost of ownership (\textit{so to speak}) and of development 
for new algorithms.  This methodology allows new algorithms to be tested in a complete framework with relative ease.

\begin{center}
\begin{figure}[here]
\includegraphics{pics/design_process.ps}
\caption{Design Flow of the First Few Original LibTomMath Functions.}
\label{pic:design_process}
\end{figure}
\end{center}

Only after the majority of the functions were in place did I pursue a less hierarchical approach to auditing and optimizing
the source code.  For example, one day I may audit the multipliers and the next day the polynomial basis functions.  

It only makes sense to begin the text with the preliminary data types and support algorithms required as well.  
This chapter discusses the core algorithms of the library which are the dependents for every other algorithm.

\section{What is a Multiple Precision Integer?}
Recall that most programming languages, in particular ISO C \cite{ISOC}, only have fixed precision data types that on their own cannot 
be used to represent values larger than their precision will allow. The purpose of multiple precision algorithms is 
to use fixed precision data types to create and manipulate multiple precision integers which may represent values 
that are very large.  

As a well known analogy, school children are taught how to form numbers larger than nine by prepending more radix ten digits.  In the decimal system
the largest single digit value is $9$.  However, by concatenating digits together larger numbers may be represented.  Newly prepended digits 
(\textit{to the left}) are said to be in a different power of ten column.  That is, the number $123$ can be described as having a $1$ in the hundreds 
column, $2$ in the tens column and $3$ in the ones column.  Or more formally $123 = 1 \cdot 10^2 + 2 \cdot 10^1 + 3 \cdot 10^0$.  Computer based 
multiple precision arithmetic is essentially the same concept.  Larger integers are represented by adjoining fixed 
precision computer words with the exception that a different radix is used.

What most people probably do not think about explicitly are the various other attributes that describe a multiple precision 
integer.  For example, the integer $154_{10}$ has two immediately obvious properties.  First, the integer is positive, 
that is the sign of this particular integer is positive as opposed to negative.  Second, the integer has three digits in 
its representation.  There is an additional property that the integer posesses that does not concern pencil-and-paper 
arithmetic.  The third property is how many digits placeholders are available to hold the integer.  

The human analogy of this third property is ensuring there is enough space on the paper to write the integer.  For example,
if one starts writing a large number too far to the right on a piece of paper they will have to erase it and move left.  
Similarly, computer algorithms must maintain strict control over memory usage to ensure that the digits of an integer
will not exceed the allowed boundaries.  These three properties make up what is known as a multiple precision 
integer or mp\_int for short.  

\subsection{The mp\_int Structure}
\label{sec:MPINT}
The mp\_int structure is the ISO C based manifestation of what represents a multiple precision integer.  The ISO C standard does not provide for 
any such data type but it does provide for making composite data types known as structures.  The following is the structure definition 
used within LibTomMath.

\index{mp\_int}
\begin{figure}[here]
\begin{center}
\begin{small}
%\begin{verbatim}
\begin{tabular}{|l|}
\hline
typedef struct \{ \\
\hspace{3mm}int used, alloc, sign;\\
\hspace{3mm}mp\_digit *dp;\\
\} \textbf{mp\_int}; \\
\hline
\end{tabular}
%\end{verbatim}