Index
k-ary exponentiation, 195
Absolute value, 42
Addition, 54
single digit, 232
Algorithm fast_mp_montgomery_reduce., 168
Algorithm fast_mult, 105
Algorithm fast_s_mp_mul_digs, 100
Algorithm fast_s_mp_sqr, 134
Algorithm mp_2expt, 214
Algorithm mp_abs, 42
Algorithm mp_add, 64
Algorithm mp_add_d, 232
Algorithm mp_clamp, 31
Algorithm mp_clear, 22
Algorithm mp_cmp, 50
Algorithm mp_cmp_mag, 48
Algorithm mp_copy, 36
Algorithm mp_div(), 221
Algorithm mp_div_2, 73
Algorithm mp_div_2d, 85
Algorithm mp_div_d, 238
Algorithm mp_dr_is_modulus, 183
Algorithm mp_dr_reduce, 179
Algorithm mp_dr_setup, 182
Algorithm mp_expt_d, 194
Algorithm mp_exptmod, 199
Algorithm mp_gcd, 259
Algorithm mp_grow, 25
Algorithm mp_init, 20
Algorithm mp_init_copy, 40
Algorithm mp_init_multi, 29
Algorithm mp_init_size, 27
Algorithm mp_invmod, 273
Algorithm mp_jacobi, 268
Algorithm mp_ktarasuba_mul, 111
Algorithm mp_karatsuba_sqr, 139
Algorithm mp_lcm, 263
Algorithm mp_lshd, 76
Algorithm mp_mod_2d, 88
Algorithm mp_montgomery_reduce, 163
Algorithm mp_montgomery_setup, 174
Algorithm mp_mul, 126
Algorithm mp_mul_2, 70
Algorithm mp_mul_2d, 82
Algorithm mp_mul_d, 235
Algorithm mp_n_root, 242
Algorithm mp_prime_fermat, 283
Algorithm mp_prime_is_divisible, 280
Algorithm mp_prime_miller_rabin, 285
Algorithm mp_rand, 246
Algorithm mp_read_radix, 249
Algorithm mp_reduce, 153
Algorithm mp_reduce_2k, 184
Algorithm mp_reduce_2k_setup, 186
Algorithm mp_reduce_is_2k, 188
Algorithm mp_reduce_setup, 157
Algorithm mp_rshd, 79
Algorithm mp_set, 45
Algorithm mp_set_int, 46
Algorithm mp_sqr, 144
Algorithm mp_sub, 67
Algorithm mp_toom_mul, 117
Algorithm mp_toradix, 252
Algorithm mp_zero, 41
Algorithm s_mp_add, 55
Algorithm s_mp_exptmod, 203
Algorithm s_mp_mul_digs, 93
Algorithm s_mp_sqr, 130
Algorithm s_mp_sub, 60
k-ary exponentiation, 195
Algorithms calling convention, See Argument passing
inputs and outputs, 6
reduction, 147
single digit helpers, 231
Aliases, See pointer aliases
Angled brackets <>, 53
Argument passing, 17–18
Arithmetic, 53
addition and subtraction, 54
bit shifting, 69
by powers of two, 81
digit shifting, 69
division by 2b, 85
division by x, 78
division by two, 72
fixed point, 148
high level addition, 63
high level subtraction, 66
low level addition, 54
low level subtraction, 59
multiplication by 2b, 82
multiplication by x, 75
multiplication by two, 69
polynomial operations, 75
Remainder of division by 2b, 88
Arithmetic on polynomials, 3
ASCII map lower, 248
Asymptotic Running Time of Polynomial Basis Multiplication, 108
B
Barrett algorithm, 153
Barrett modular exponentiation, 203
choosing a radix point, 150
setup, 156
trimming the quotient, 151
trimming the residue, 152
Barrett, Paul, 97
big-Oh, 7
Bignum math, 2
Bit shifting, 53
bn_mp_lshd(), 76
Brackets in mathematical expressions, 6
C programming language Data types, 2
Carmichael numbers, 282
Code, See Source code
Code Base, 10–11
Comba method, 94
fixup algorithm, 98
multiplication with, 97
squaring with, 133
Comba, Paul, 97
Comparing modular reduction algorithms, 189
signed comparisons, 50
unsigned comparisons, 47
Comparisons, See Comparing
Constants, 44
setting large, 46
setting small, 44
Data types definition, 13
high precision floating point, 2
precision notation, 6
Destinations allowing arguments sources to be, 18
Digit shifting, 53
Division by power of two, 85
integer, with remainder, 217
normalized integers, 220
quotient estimation, 219
radix-βwith remainder, 221
remainder of division by power of two, 88
single digit, 237
Downloading LibTomMath library, 12
E
ECC, See Elliptic Curve Cryptography
Elliptic curve cryptography, 3
Errors trapping runtime, 18
Exponentiation, 203
k-ary, 195
Barrett modular, 203
modular, 198
overview, 191
power of two, 214
single digit, 193
sliding window, 197
Expressions precision notation, 6
Fast multiplication, 105
fast_mp_invmod(), 275
fast_mp_montgomery_reduce(), 169
fast_s_mp_mul_digs(), 101
fast_s_mp_sqr(), 135
Fixed point arithmetic, 148
Floating point math, See high precision
floating point Formatted Representations, 247
Integer comparing signed, 50
comparing unsigned, 47
division, 218
division with remainder, 217
greatest common divisor, 255
Jacobi symbol, 265
least common multiple, 263
modular inverse, 271
negation, 43
Least common multiple, 263
Left to Right Exponentiation, 192
Legendre function, 265
Libraries writing useful source code, 13
LibTom, xv
Public Domain, xv
LibTomMath, 9
LibTomMath library, 4
Linear feedback shift register, 263
Maintenance Algorithms, 24
Measuring algorithms′ efficiency, 7
Memory management algorithms, 15
multiple precision Algorithm overhead, 3
Miller-Rabin test, 284
Mirror points, 108
Modular exponentiation, 198
Modular inversion, 271
Modular reduction Algorithm compared, 189
Barrett algorithm, 153
Barrett reduction, 148
diminished radix algorithm, 175
Montgomery reduction, 158
overview, 147
Modular residue, 147
Modularity of projects, 13
baseline, 162
digit based, 160
Faster “Comba”, 167
mp_2expt(), 214
mp_abs(), 42
mp_add(), 65
mp_add_d(), 232
mp_clamp(), 32
mp_clear(), 23
mp_cmp(), 51
mp_cmp_mag(), 49
mp_copy(), 36
mp_digit, 6
mp_div(), 224
mp_div_2(), 73
mp_div_2d(), 85
mp_div_d(), 238
mp_dr_is_modulus(), 183
mp_dr_reduce(), 180
mp_dr_setup(), 182
mp_expt_d(), 194
mp_gcd(), 260
mp_grow(), 25
mp_init(), 21
mp_init_copy(), 40
mp_init_multi(), 29
mp_init_size(), 27
mp_int structure, 15–17
assigning value, 35
augmenting precision, 24
clamping, 31
clearing, 22
copying, 35
creating a clone (copy), 39
initializing, 19
initializing variable precision, 27
zeroing, 41
mp_invmod(), 275
mp_jacobi(), 269
mp_karatsuba_mul(), 112
mp_karatsuba_sqr(), 140
mp_lcm(), 264
MP_MEM, 18
mp_mod_2d(), 88
mp_montgomery_reduce(), 164
mp_montgomery_setup(), 174
mp_mul(), 127
mp_mul_2(), 71
mp_mul_2d(), 83
mp_mul_d(), 236
mp_n_root(), 242
MP_NEG, 16
mp_neg(), 44
MP_OKAY, 18
mp_prime_fermat(), 283
mp_prime_is_divisible(), 280
mp_prime_miller_rabin(), 285
mp_rand(), 246
mp_read_radix(), 249
mp_reduce(), 154
mp_reduce_2k(), 184
mp_reduce_2k_setup(), 186
mp_reduce_is_2k(), 188
mp_reduce_setup(), 157
mp_rshd(), 79
mp_set(), 45
mp_set_int(), 46
mp_sqr(), 144
mp_sub(), 68
mp_toom_mul(), 119
mp_toradix(), 253
MP_VAL, 18
mp_word, 6
mp_zero(), 41
MP_ZPOS, 16
MSVC pointer arithmetic, 39
Multiple integer initialization and clearing, 29
Multiple Precision Arithmetic Initialization and clearing, 19
notation, 5–7
overview, 1–4
Multiple precision integers, 14–17
Multiplication baseline multiplication, 92
by power of two, 82
Comba method, 97
polynomial basis, 107
polynomial basis squaring, 138
signed, 126
single digit, 235
squaring, 128
the multipliers, 91
Toom-Cook Algorithm, 116
Multiplication Algorithm mp_mul(), 9
Pointer aliases, 38
Pointer arithmetic, 39
Polynomial basis, 3
multiplication, 107
squaring, 138
Portability, 12
Power of two, 214
precision, 3
Primality tests, 279
Fermat test, 282
Miller-Rabin test, 284
trial division, 279
Prime numbers tests, 279
pseudo-code, 4
Public key cryptography, 2
R
Radix Point, 111
Radix-n input reading, 247
Random number generation, 245
Representations formatted, 247
Return values, 18
Rose, Greg, xviii
RSA Algorithm, 2
Runtime errors, 18
s_mp_add(), 56
s_mp_exptmod(), 207
s_mp_mul_digs(), 95
s_mp_sqr(), 131
s_mp_sub(), 61
Scoring system book’s exercises, 8
Sign manipulation, 42
Signed addition, See High level addition
Signed comparisons, 50
Signed subtraction, See High level subtraction
Single digit division, 237
exponentiation, 193
multiplication, 235
root extraction, 241
Sliding Window Exponentiation, 198
source, See Source code
Source code header files, 13
modular design, 13
precision data types in, 6
return values, 18
writing useful libraries, 13
Speed measuring algorithms′, 7
Squaring Comba method, 133
high level, 144
Karatsuba, 138
polynomial basis, 138
Stability, 12
Subtraction, 54
single digit, 232
..................Content has been hidden....................
You can't read the all page of ebook, please click here login for view all page.