libtom (original) (raw)

LibTomMath is a free open source portable number theoretic multiple-precision integer library written entirely in C. (phew!). 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.

The library provides a vast array of highly optimized 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 optimizations throughout the entire library.