hcrypto/libtommath/tommath.tex

177 the decimal system with fixed precision $6 \cdot 7 = 2$.
235 precision algorithm would augment the precision of the destination to accomodate the result while a single precision system
240 size the system will ever need.  Such an approach can lead to vastly simpler algorithms which can accomodate the
349 To measure the efficiency of the specified algorithms, a modified big-Oh notation is used.  In this system all
375 Similar to the exercises of \cite[pp. ix]{TAOCPV2} these exercises are given a scoring system based on the difficulty of
378 scoring system used.
476 which allows the reader to find a given function very quickly.  On average there are $76$ lines of code per source
493 The GMP library also does not return error codes.  Instead it uses a POSIX.1 \cite{POSIX1} signal system where errors
549 \includegraphics{pics/design_process.ps}
567 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
705 temporary mp\_ints, and return as soon as possible.  The goal is to leave the system in the same state it was when the
1063 \textbf{used} count until a non-zero most significant digit is found.  Also in this system, zero is considered to be a
1226 work for GCC and not MSVC.  As such it is ideal to find a common ground for as many compilers as possible.  Pointer
1734 Similar to the implementation of mp\_copy this function uses the braced code and local aliases coding style.  The three aliases that are on
2020 In a binary system where the radix is a power of two multiplication by two not only arises often in other algorithms it is a fairly efficient
2190 \includegraphics{pics/sliding_window.ps}
2470 $\left [ 2 \right ] $ & Devise a chart to find optimal values of $k$ for the previous problem \\
2784 $ix$ is.  This is used for the immediately subsequent statement where we find $iy$.
2826 $g(x) = \sum_{i=0}^{n} b_i x^i$ respectively, is required.  In this system both $f(x)$ and $g(x)$ have $n + 1$ terms and are of the $n$'th degree.
2892 the algorithms incur an overhead (\textit{at the $O(n)$ work level}) since they require a system of equations to be solved.  This makes the
2906 \item  The complexity of the linear system of equations (\textit{for the coefficients of $W(x)$}) is.  Generally speaking as the number of splits
2907 grows the complexity grows substantially.  Ideally solving the system will only involve addition, subtraction and shifting of integers.  This
2931 $\zeta_0$, $\zeta_{\infty}$ and $\zeta_{1}$.  Consider the resultant system of equations.
2942 of this system of equations has made Karatsuba fairly popular.  In fact the cutoff point is often fairly low\footnote{With LibTomMath 0.18 it is 70 and 109 digits for the Intel P4 and AMD Athlon respectively.}
3011 The new coding element in this routine, not  seen in previous routines, is the usage of goto statements.  The conventional
3034 chosen such that $\zeta$ is easy to compute and the resulting system of equations easy to reduce.  Here, the points $\zeta_{0}$,
3038 With the five relations that Toom-Cook specifies, the following system of equations is formed.
3100 Now solve the system of equations. \\
3129 integers the coefficients of the polynomial basis representations $f(x)$ and $g(x)$ are known and can be used to find the relations required.
3132 to the points $16 \cdot \zeta_{1 \over 2}, \zeta_{2}$ and $\zeta_{1}$ respectively.  These are found using logical shifts to independently find
3135 After the five relations $w_0, w_1, \ldots, w_4$ have been computed, the system they represent must be solved in order for the unknown coefficients
3136 $w_1, w_2$ and $w_3$ to be isolated.  The steps 18 through 25 perform the system reduction required as previously described.  Each step of
3162 After this point we solve for the actual values of $w1, w2$ and $w3$ by reducing the $5 \times 5$ system which is relatively
3411 multiplications to find the $\zeta$ relations, squaring operations are performed instead.
3523 This routine uses the same error trap coding style as mp\_karatsuba\_sqr.  As the temporary variables are initialized errors are
3529 instead of multiplication to find the five relations.  The reader is encouraged to read the description of the latter algorithm and try to
3637 In this system a $k$-bit integer $n$ would actually represent $n/2^q$.  For example, with $q = 4$ the integer $n = 37$ would actually represent the
3678 another $n^2$ single precision multiplications to find the residue.  In total $3n^2$ single precision multiplications are required to
3691 Let $a$ represent the number of which the residue is sought.  Let $b$ represent the modulus used to find the residue.  Let $m$ represent
3717 precision multiplications, ignoring the subtractions required.  In total $2m^2 + m$ single precision multiplications are required to find the residue.
4370 three passes were required to find the residue $x \equiv 126$.
4574 The algorithm mp\_count\_bits calculates the number of bits in an mp\_int which is used to find the initial value of $p$.  The call to mp\_div\_2d
5061 Setup the table of small powers of $g$.  First find $g^{2^{winsize}}$ and then all multiples of it. \\
5182 \includegraphics{pics/expt_state.ps}
5288 To find the first digit of the quotient the value of $k$ must be maximized such that $kx\beta^t$ is less than or equal to $y$ and
5290 used to find the maximum is to ``eyeball'' the two numbers, typically only the leading digits and quickly estimate a quotient.  By only using leading
5408 Now find the remainder fo the digits. \\
5666 compiler does not recognize that optimization and will actually produce two function calls to find the quotient and remainder respectively.
5722 $x^{b - 1}$.  This value can then be multiplied by $x$ and have $a$ subtracted from it to find the numerator.  This saves a total of $b - 1$
5726 root.  Ideally this algorithm is meant to find the $n$'th root of an input where $n$ is bounded by $2 \le n \le 5$.
5738 factoring for example, can make use of random values as starting points to find factors of a composite integer.  In this case the algorithm presented
5992 However, instead of factoring $b - a$ to find a suitable value of $p$ the powers of $p$ can be removed from $a$ and $b$ that are in common first.
6127 The least common multiple arises often in coding theory as well as number theory.  If two functions have periods of $a$ and $b$ respectively they will
6448 the Diophantine $Cb + Da = 1$ only $B$ and $D$ are required to find the inverse of $a$.