blob: 46dc2a313a6761f95b0865e0e04f888259c7e12e (
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.42.0
SOURCE_HASH=sha512:c5bb26a260477de4e9abee9f65735754efa69c39c89caa3a06dd8ad3eda9d27fff687a432e91e3410b2bcc6a9e3d59921b6cdf6ca7f1ca6c69ed199a002e5790
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
LICENSE[0]=WTFPL
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
|
