LibTomMath 0.40

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.

What's New in This Release:

· This release fixes one overflow and a minor build issue.
· Otherwise, the code is stable and unchanged.



Product's homepage