lib/tommath/bn.tex

76 large integer numbers.  It was written in portable ISO C source code so that it will build on any platform with a conforming
79 In a nutshell the library was written from scratch with verbose comments to help instruct computer science students how
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
86 release the textbook ``Implementing Multiple Precision Arithmetic'' has been placed in the public domain with every new
91 public domain everyone is entitled to do with them as they see fit.
95 LibTomMath is meant to be very ``GCC friendly'' as it comes with a makefile well suited for GCC.  However, the library will
106 that and include ``tommath.h'' within your programs.  Alternatively to build with MSVC issue the following
111 This will build the library and archive the object files in ``tommath.lib''.  This has been tested with MSVC
112 version 6.00 with service pack 5.
125 Cygwin to work with since it requires the auto-export/import functionality.  The resulting DLL and import library
152 will exit with a dump of the relevent numbers it was working with.
165 another pre--defined class ``SC\_RSA\_1'' which works in conjunction with the RSA from LibTomCrypt.  Additional
196 RSA cryptography you only require exponentiation with odd moduli so even moduli support can be safely removed.
205 \hline Exponentiation with odd moduli only & BN\_S\_MP\_EXPTMOD\_C \\
210 \hline Exponentiation with random odd moduli & (The above plus the following) \\
245 Unlike  GNU MP (GMP) Library, LIP, OpenSSL or various other commercial kits (Miracl), LibTomMath was not written with
281 However, LibTomMath was written with cryptography in mind.  It provides essentially all of the functions a cryptosystem
282 would require when working with large integers.
292 be performed with as little as 8KB of ram for data (again depending on build options).
294 \chapter{Getting Started with LibTomMath}
377 A single mp\_int can be initialized with the ``mp\_init'' function.
407 When you are finished with an mp\_int it is ideal to return the heap it used back to the system.  The following function
433    /* We're done with it. */
473    /* We're done with them. */
507    /* We're done with them. */
514 Another less common initializer is mp\_init\_size() which allows the user to initialize an mp\_int with a given
549 digits can be removed to return memory to the heap with the mp\_shrink() function.
575    /* We're done with it for now. */
585    /* we're done with it. */
632    /* we're done with it. */
648 Setting a single digit can be accomplished with the following function.
674    /* we're done with it. */
725    /* we're done with it. */
849    /* we're done with it. */
907    /* we're done with it. */
957    /* we're done with it. */
972 Logical operations are operations that can be performed either with simple shifts or boolean operators such as
977 Multiplications and divisions by any power of two can be performed with quick logical shifts either left or
1029    /* we're done with it. */
1118 Simple integer negation can be performed with the following.
1128 Simple integer absolutes can be performed with the following.
1138 To perform a complete and general integer division with remainder use the following function.
1152 A full signed integer multiplication can be performed with the following.
1159 should only be used with very large inputs.  This is followed by the Karatsuba multiplications which are for moderate
1234 multiplications with Toom-Cook or 100,000,000 single precision multiplications with the standard Comba (a factor
1238 actually faster than Comba until you hit distinct  ``cutoff'' points.  For Karatsuba with the default configuration,
1246 can be built with GCC as follows
1298 This reduces $a$ modulo $b$ and stores the result in $c$.  The sign of $c$ shall agree with the sign
1304 a decent speedup over straight division.  First a $\mu$ value must be precomputed with the following function.
1312 be computed once.  Modular reduction can now be performed with the following.
1319 This will reduce $a$ in place modulo $b$ with the precomputed $\mu$ value in $c$.  $a$ must be in the range
1378 step is required.  This is accomplished with the following.
1385 For the given odd moduli $a$ the precomputation value is placed in $mp$.  The reduction is computed with the
1392 This reduces $a$ in place modulo $m$ with the pre--computed value $mp$.   $a$ must be in the range
1495 ``Dimminished Radix'' reduction refers to reduction with respect to moduli that are ameniable to simple
1507 and does not return any error codes.  After the pre--computation a reduction can be performed with the
1515 This reduces $a$ in place modulo $b$ with the pre--computed value $mp$.  $b$ must be of a restricted
1544 This will reduce $a$ in place modulo $n$ with the pre--computed value $d$.  From my experience this routine is
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}$
1614 fool (besides with Carmichael numbers).  If $a$ passes the test (therefore is probably prime) $result$ is set to one.
1621 Generally to ensure a number is very likely to be prime you have to perform the Miller-Rabin with at least a half-dozen
1649 This finds the next prime after $a$ that passes mp\_prime\_is\_prime() with $t$ tests.  Set $bbs\_style$ to one if you
1765 They operate essentially the same as the unsigned copies except they prefix the data with zero or non--zero
1804 This will compute the Jacobi symbol for $a$ with respect to $p$.  If $p$ is prime this essentially computes the Legendre
1830 functions fairly handy if you have to work with relatively small numbers since you will not have to allocate