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 to fairly efficient routines from various branches of
number theory:
* 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.
WWW: http://libtom.net/
None
None