2.5 Initialization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
2.5.1 Single Initialization . . . . . . . . . . . . . . . . . . . . . . 11
2.3 Data Types . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.4 Function Organization . . . . . . . . . . . . . . . . . . . . . . . . 10
7.5 Next Prime . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
7.6 Random Primes . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
1.4 Build Configuration . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.4.1 Build Depends . . . . . . . . . . . . . . . . . . . . . . . . 4
1.4.2 Build Tweaks . . . . . . . . . . . . . . . . . . . . . . . . . 4
3.3 Logical Operations . . . . . . . . . . . . . . . . . . . . . . . . . . 26
3.3.1 Multiplication by two . . . . . . . . . . . . . . . . . . . . 26
3.3.2 Polynomial Basis Operations . . . . . . . . . . . . . . . . 28
7.6.1 Extended Generation . . . . . . . . . . . . . . . . . . . . . 47
8 Input and Output
49
8.1 ASCII Conversions . . . . . . . . . . . . . . . . . . . . . . . . . . 49
6.2 Modular Exponentiation . . . . . . . . . . . . . . . . . . . . . . . 43
6.3 Root Finding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
5.2 Barrett Reduction . . . . . . . . . . . . . . . . . . . . . . . . . . 36
5.3 Montgomery Reduction . . . . . . . . . . . . . . . . . . . . . . . 37
5.4 Restricted Dimminished Radix . . . . . . . . . . . . . . . . . . . 40
3.2.1 Unsigned comparison . . . . . . . . . . . . . . . . . . . . . 23
3.2.2 Signed comparison . . . . . . . . . . . . . . . . . . . . . . 24
3.2.3 Single Digit . . . . . . . . . . . . . . . . . . . . . . . . . . 25
2.6 Maintenance Functions . . . . . . . . . . . . . . . . . . . . . . . . 15
2.6.1 Reducing Memory Usage . . . . . . . . . . . . . . . . . . 15
2.6.2 Adding additional digits . . . . . . . . . . . . . . . . . . . 16
4 Multiplication and Squaring
31
4.1 Multiplication . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
4.2 Squaring . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
9
2.1 Building Programs . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.2 Return Codes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.2 License . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.3 Building LibTomMath . . . . . . . . . . . . . . . . . . . . . . . . 2
2.5.2 Single Free . . . . . . . . . . . . . . . . . . . . . . . . . . 11
2.5.3 Multiple Initializations . . . . . . . . . . . . . . . . . . . . 12
2.5.4 Other Initializers . . . . . . . . . . . . . . . . . . . . . . . 13
3.5.1 Negation . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
3.5.2 Absolute . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
3.6 Integer Division and Remainder . . . . . . . . . . . . . . . . . . . 30
1.4.3 Build Trims . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.5 Purpose of LibTomMath . . . . . . . . . . . . . . . . . . . . . . . 5
2 Getting Started with LibTomMath
iii
3 Basic Operations
19
3.1 Small Constants . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
3.1.1 Single Digit . . . . . . . . . . . . . . . . . . . . . . . . . . 19
5.5 Unrestricted Dimminshed Radix . . . . . . . . . . . . . . . . . . 41
6 Exponentiation
43
6.1 Single Digit Exponentiation . . . . . . . . . . . . . . . . . . . . . 43
1.3.1 Static Libraries . . . . . . . . . . . . . . . . . . . . . . . . 2
1.3.2 Shared Libraries . . . . . . . . . . . . . . . . . . . . . . . 2
1.3.3 Testing . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
7 Prime Numbers
45
7.1 Trial Division . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
7.2 Fermat Test . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
3.1.2 Long Constants . . . . . . . . . . . . . . . . . . . . . . . . 20
3.1.3 Initialize and Setting Constants . . . . . . . . . . . . . . . 21
3.2 Comparisons . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
Open Source. Open Academia. Open Minds. Tom St Denis,
Ontario, Canada
Contents
1 Introduction
1
1.1 What is LibTomMath? . . . . . . . . . . . . . . . . . . . . . . . . 1
4.3 Tuning Polynomial Basis Routines . . . . . . . . . . ction