Lines Matching refs:Of
75 LibTomMath is a library of source code which provides a series of efficient and carefully written functions for manipulating
81 universities, commercial and open source software developers. It has been used on a variety of platforms ranging from
85 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
87 release as well. This textbook is meant to compliment the project by providing a more solid walkthrough of the development
96 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
136 results. ``mtest/mtest'' will generate test vectors using the MPI library by Michael Fromberger\footnote{A copy of MPI
150 This will output a row of numbers that are increasing. Each column is a different test (such as addition, multiplication, etc)
152 will exit with a dump of the relevent numbers it was working with.
160 instructs the system to build all of the functions. This is how LibTomMath used to be packaged. This will give you
164 don't need the vast majority of the library to perform these operations. Aside from LTM\_ALL there is
166 classes can be defined base on the need of the user.
169 In the file tommath\_class.h you will see a large list of C ``defines'' followed by a series of ``ifdefs''
170 which further define symbols. All of the symbols (technically they're macros $\ldots$) represent a given C source
181 They can be enabled at any pass of the configuration phase.
195 A trim is a manner of removing functionality from a function that is not required. For instance, to perform
197 Build trims are meant to be defined on the last pass of the configuration which means they are to be defined
244 \section{Purpose of LibTomMath}
251 LibTomMath was written to be an instructive collection of source code. This is why there are many comments, only one
259 are the pros and cons of LibTomMath by comparing it to the math routines from GnuPG\footnote{GnuPG v1.2.3 versus LibTomMath v0.28}.
266 \hline Few lines of code per file & X & & GnuPG $ = 300.9$, LibTomMath $ = 71.97$ \\
271 \hline Five modular reduction algorithms & X & & Faster modular exponentiation for a variety of moduli. \\
280 It may seem odd to compare LibTomMath to GnuPG since the math in GnuPG is only a small portion of the entire application.
281 However, LibTomMath was written with cryptography in mind. It provides essentially all of the functions a cryptosystem
284 So it may feel tempting to just rip the math code out of GnuPG (or GnuMP where it was taken from originally) in your
286 not normally significantly slower. On x86 machines the difference is normally a factor of two when performing modular
290 on the other side of the coin LibTomMath offers you a totally free (public domain) well structured math library
292 be performed with as little as 8KB of ram for data (again depending on build options).
322 provide the address of an integer it can store to) which the caller can access. To convert one of the three return codes
335 organize all of the data required to manipulate the integer it represents. Within LibTomMath it has been prototyped
346 Where ``mp\_digit'' is a data type that represents individual digits of the integer. By default, an mp\_digit is the
356 The arithmetic functions of the library are all organized to have the same style prototype. That is source operands
365 Another feature of the way the functions have been implemented is that source operands can be destination operands as well.
384 This function expects a pointer to an mp\_int structure and will initialize the members of the structure so the mp\_int
441 Certain algorithms require more than one large integer. In these instances it is ideal to initialize all of the mp\_int
452 It accepts a \textbf{NULL} terminated list of pointers to mp\_int structures. It will attempt to initialize them all
453 at once. If the function returns MP\_OKAY then all of the mp\_int variables are ready to use, otherwise none of them
481 To initialized and make a copy of an mp\_int the mp\_init\_copy() function has been provided.
488 This function will initialize $a$ and make it a copy of $b$ if all goes well.
498 /* We want a copy of num1 in num2 now */
505 /* now num2 is ready and contains a copy of num1 */
515 default number of digits. By default, all initializers allocate \textbf{MP\_PREC} digits. This function lets
556 This will remove excess digits of the mp\_int $a$. If the operation fails the mp\_int should be intact without the
594 Within the mp\_int structure are two parameters which control the limitations of the array of digits that represent
596 contribute to the value of the mp\_int. The \textit{alloc} parameter dictates how many digits are currently available in
605 This will grow the array of digits of $a$ to $size$. If the \textit{alloc} parameter is already bigger than
644 domain of a digit can change (it's always at least $0 \ldots 127$).
655 This will zero the contents of $a$ and make it represent an integer equal to the value of $b$. Note that this
656 function has a return type of \textbf{void}. It cannot cause an error so it is safe to assume the function
683 To set a constant that is the size of an ISO C ``unsigned long'' and larger than a single digit the following function
691 This will assign the value of the 32-bit variable $b$ to the mp\_int $a$. Unlike mp\_set() this function will always
692 accept a 32-bit input regardless of the size of a single digit. However, since the value may span several digits
693 this function can fail if it runs out of heap memory.
695 To get the ``unsigned long'' copy of an mp\_int the following function can be used.
702 This will return the 32 least significant bits of the mp\_int $a$.
718 printf("Error setting the value of the number. \%s",
804 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
809 An unsigned comparison considers only the digits themselves and not the associated \textit{sign} flag of the
817 This will compare $a$ to $b$ placing $a$ to the left of $b$. This function cannot fail and will return one of the
874 This will compare $a$ to the left of $b$. It will first compare the signs of the two mp\_int variables. If they
876 individually. This function will return one of the compare conditions codes listed in figure \ref{fig:CMP}.
930 This will compare $a$ to the left of $b$ using a signed comparison. Note that it will always treat $b$ as
932 comes up in cryptography). The function cannot fail and will return one of the tree compare condition codes
977 Multiplications and divisions by any power of two can be performed with quick logical shifts either left or
1043 Since $10 > 7$ and $5 < 7$. To multiply by a power of two the following function can be used.
1050 This will multiply $a$ by $2^b$ and store the result in ``c''. If the value of $b$ is less than or equal to
1053 To divide by a power of two use the following.
1065 Strictly speaking the organization of the integers within the mp\_int structures is what is known as a
1066 ``polynomial basis''. This simply means a field element is stored by divisions of a radix. For example, if
1067 $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
1068 the polynomial basis representation of $z$ if $f(\beta) = z$ for a given radix $\beta$.
1070 To multiply by the polynomial $g(x) = x$ all you have todo is shift the digits of the basis left one place. The
1079 in the least significant digits. Similarly to divide by a power of $x$ the following function is provided.
1100 Which compute $c = a \odot b$ where $\odot$ is one of OR, AND or XOR.
1112 Which perform $c = a \odot b$ where $\odot$ is one of signed addition or subtraction. The operations are fully sign
1146 $bc + d = a$. Note that either of $c$ or $d$ can be set to \textbf{NULL} if their value is not required. If
1157 Which assigns the full signed product $ab$ to $c$. This function actually breaks into one of four cases which are
1217 Since squaring can be performed faster than multiplication it is performed it's own function instead of just using
1225 Will square $a$ and store it in $b$. Like the case of multiplication there are four different squaring
1227 of the speed difference.
1231 Both of the Toom-Cook and Karatsuba multiplication algorithms are faster than the traditional $O(n^2)$ approach that
1235 of 138).
1245 A demo program in the ``etc/'' directory of the project called ``tune.c'' can be used to find the cutoff points. This
1251 Where ``XXX'' is one of the following entries from the table \ref{fig:tuning}.
1257 \hline \textbf{Value of XXX} & \textbf{Meaning} \\
1270 When the program is running it will output a series of measurements for different cutoff points. It will first find
1276 Modular reduction is process of taking the remainder of one quantity divided by another. Expressed
1277 as (\ref{eqn:mod}) the modular reduction is equivalent to the remainder of $b$ divided by $c$.
1284 Of particular interest to cryptography are reductions where $b$ is limited to the range $0 \le b < c^2$ since particularly
1287 Note that one of the four optimized reduction algorithms are automatically chosen in the modular exponentiation
1298 This reduces $a$ modulo $b$ and stores the result in $c$. The sign of $c$ shall agree with the sign
1299 of $b$. This algorithm accepts an input $a$ of any range and is not limited by $0 \le a < b^2$.
1400 where $R = \beta^n$, $n$ is the n number of digits in $m$ and $\beta$ is radix used (default is $2^{28}$).
1411 example, to calculate $a^3 \mbox { mod }b$ using Montgomery reduction the value of $a$ can be normalized by
1487 This particular example does not look too efficient but it demonstrates the point of the algorithm. By
1488 normalizing the inputs the reduced results are always of the form $aR$ for some variable $a$. This allows
1496 digit shifting and small multiplications. In this case the ``restricted'' variant refers to moduli of the
1499 As in the case of Montgomery reduction there is a pre--computation phase required for a given modulus.
1515 This reduces $a$ in place modulo $b$ with the pre--computed value $mp$. $b$ must be of a restricted
1523 Note that unlike Montgomery reduction there is no normalization process. The result of this function is
1528 Unrestricted reductions work much like the restricted counterparts except in this case the moduli is of the
1530 can be applied to a wider range of numbers.
1554 $a$ for all values of $b$ greater than three.
1562 will automatically detect the fastest modular reduction technique to use during the operation. For negative values of
1568 moduli of the a ``restricted dimminished radix'' form lead to the fastest modular exponentiations. Followed by Montgomery
1576 This computes $c = a^{1/b}$ such that $c^b \le a$ and $(c+1)^b > a$. The implementation of this function is not
1577 ideal for values of $b$ greater than three. It will work but become very slow. So unless you are working with very small
1579 a root with the sign of the input for odd roots. For example, performing $4^{1/2}$ will return $2$ whereas $(-8)^{1/3}$
1583 the algorithm requires raising $a$ to the power of $b$ it is not ideal to attempt to find roots for large
1584 values of $b$. If particularly large roots are required then a factor method could be used instead. For example,
1594 This will attempt to evenly divide $a$ by a list of primes\footnote{Default is the first 256 primes.} and store the
1613 Performs a Miller-Rabin test to the base $b$ of $a$. This test is much stronger than the Fermat test and is very hard to
1617 Note that is suggested that you use the Miller-Rabin test instead of the Fermat test since all of the failures of
1618 Miller-Rabin are a subset of the failures of the Fermat test.
1620 \subsection{Required Number of Tests}
1622 or so unique bases. However, it has been proven that the probability of failure goes down as the size of the input goes up.
1629 This returns the number of trials required for a $2^{-96}$ (or lower) probability of failure for a given ``size'' expressed
1640 This will perform a trial division followed by $t$ rounds of Miller-Rabin tests on $a$ and store the result in $result$.
1641 If $a$ passes all of the tests $result$ is set to one, otherwise it is set to zero. Note that $t$ is bounded by
1642 $1 \le t < PRIME\_SIZE$ where $PRIME\_SIZE$ is the number of primes in the prime number table (by default this is $256$).
1659 $t$ rounds of tests. The ``ltm\_prime\_callback'' is a typedef for
1667 mp\_prime\_random() is more suitable for generating primes which must be secret (as in the case of RSA) since there
1670 \textit{Note:} As of v0.30 of the LibTomMath library this function has been deprecated. It is still available
1680 This will generate a prime in $a$ using $t$ tests of the primality testing algorithms. The variable $size$
1681 specifies the bit length of the prime desired. The variable $flags$ specifies one of several options available
1712 This still store $a$ in ``str'' as a base-``radix'' string of ASCII chars. This function appends a NUL character
1713 to terminate the string. Valid values of ``radix'' line in the range $[2, 64]$. To determine the size (exact) required
1720 This stores in ``size'' the number of characters (including space for the NUL terminator) required. Upon error this
1741 This will return the number of bytes (octets) required to store the unsigned copy of the integer $a$.
1748 requires. It does not store the sign of the integer.
1754 This will read in an unsigned big--endian array of bytes (octets) from $b$ of length $c$ into $a$. The resulting
1757 For those who acknowledge the existence of negative numbers (heretic!) there are ``signed'' versions of the
1783 Any of the U1/U2/U3 paramters can be set to \textbf{NULL} if they are not desired.
1790 This will compute the greatest common divisor of $a$ and $b$ and store it in $c$.
1797 This will compute the least common multiple of $a$ and $b$ and store it in $c$.
1805 symbol. The result is stored in $c$ and can take on one of three values $\lbrace -1, 0, 1 \rbrace$. If $p$ is prime
1814 Computes the multiplicative inverse of $a$ modulo $b$ and stores the result in $c$ such that $ac \equiv 1 \mbox{ (mod }b\mbox{)}$.
