LibTomMath 0.37 review

LibTomMath is a free open source portable number theoretic multiple-precision integer library written entirely in C

License: GPL (GNU General Public License) File size: 1879K Developer: Tom St Denis

0

LibTomMath is a free open source portable number theoretic multiple-precision integer library written entirely in C. The library is designed to provide a simple to work with API that provides fairly efficient routines that build out of the box without configuration.

The library builds out of the box with GCC 2.95 [and up] as well as Visual C++ v6.00 [with SP5] without configuration. The source code is arranged to make it easy to dive into a particular area very quickly.

The code is also littered with comments [This is one of the on going goals] that help explain the algorithms and their implementations. Ideally the code will serve as an educational tool in the future for CS students studying number theory.

Here are some key features of "LibTomMath":
Simple Algebraic

Addition
Subtraction
Multiplication
Squaring
Division

Digit Manipulation

Shift left/right whole digits (mult by 2b by moving digits)
Fast multiplication/division by 2 and 2k for k>1
Binary AND, OR and XOR gates

Modular Reductions

Barrett Reduction (fast for any p)
Montgomery Reduction (faster for any odd p)
DR Reduction (faster for any restricted p see manual)
2k Reduction (fast reduction modulo 2p - k for k < MP_MASK and for k > MP_MASK)
The exptmod logic can use any of the five reduction algorithms when appropriate with a single function call.

Number Theoretic

Greatest Common Divisor
Least Common Multiple
Jacobi Symbol Computation (falls back to Legendre for prime moduli)
Multiplicative Inverse
Extended Euclidean Algorithm
Modular Exponentiation
Fermat and Miller-Rabin Primality Tests, utility function such as is_prime and next_prime

Miscellaneous

Root finding over Z
Pseudo-random integers
Signed and Unsigned comparisons

Optimizations

Fast Comba based Multiplier, Squaring and Montgomery routines.
Montgomery, Diminished Radix and Barrett based modular exponentiation.
Karatsuba and Toom-Cook multiplication algorithms.
Many pointer aliasing optimiztions throughout the entire library.