blob: 6ee1ed8393b4fde32a2d4940babbb133b83d0c29 (
plain) (
blame)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
|
SPELL=libtommath
VERSION=0.41
PATCHLEVEL=1
SOURCE=ltm-$VERSION.tar.bz2
SOURCE2=$SOURCE.asc
SOURCE2_IGNORE=signature
SOURCE_DIRECTORY=$BUILD_DIRECTORY/$SPELL-$VERSION
SOURCE_URL=http://libtom.org/files/$SOURCE
SOURCE2_URL=$SOURCE_URL.asc
SOURCE_HASH=signature
SOURCE_GPG=ltm.gpg:$SOURCE2:UPSTREAM_KEY
WEB_SITE=http://libtom.org/?page=index&newsitems=5&whatfile=ltm
LICENSE[0]=GPL
ENTERED=20070222
SHORT="LibTomMath is a free open source portable number theoretic multiple-precision integer library."
cat << EOF
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
o Addition o Subtraction o Multiplication o Squaring o Division
* Digit Manipulation
o Shift left/right whole digits (mult by 2b by moving digits)
o Fast multiplication/division by 2 and 2k for k>1 o Binary AND,
OR and XOR gates
* Modular Reductions
o Barrett Reduction (fast for any p) o Montgomery Reduction (faster
for any odd p) o DR Reduction (faster for any restricted p see
manual) o 2k Reduction (fast reduction modulo 2p - k for k < MP_MASK
and for k > MP_MASK) o The exptmod logic can use any of the five
reduction algorithms when appropriate with a single function call.
* Number Theoretic
o Greatest Common Divisor o Least Common Multiple o Jacobi
Symbol Computation (falls back to Legendre for prime moduli) o
Multiplicative Inverse o Extended Euclidean Algorithm o Modular
Exponentiation o Fermat and Miller-Rabin Primality Tests, utility
function such as is_prime and next_prime
* Miscellaneous
o Root finding over Z o Pseudo-random integers o Signed and
Unsigned comparisons
* Optimizations
o Fast Comba based Multiplier, Squaring and Montgomery routines.
o Montgomery, Diminished Radix and Barrett based modular
exponentiation. o Karatsuba and Toom-Cook multiplication algorithms.
o Many pointer aliasing optimiztions throughout the entire library.
EOF
|
