Computational number theory

Developed from the author's popular graduate-level course, Computational Number Theory presents a complete treatment of number-theoretic algorithms. Avoiding advanced algebra, this self-contained text is designed for advanced undergraduate and beginning graduate students in engineering. It is also suitable for researchers new to the field and practitioners of cryptography in industry.

Requiring no prior experience with number theory or sophisticated algebraic tools, the book covers many computational aspects of number theory and highlights important and interesting engineering applications. It first builds the foundation of computational number theory by covering the arithmetic of integers and polynomials at a very basic level. It then discusses elliptic curves, primality testing, algorithms for integer factorization, computing discrete logarithms, and methods for sparse linear systems. The text also shows how number-theoretic tools are used in cryptography and cryptanalysis. A dedicated chapter on the application of number theory in public-key cryptography incorporates recent developments in pairing-based cryptography.

With an emphasis on implementation issues, the book uses the freely available number-theory calculator GP/PARI to demonstrate complex arithmetic computations. The text includes numerous examples and exercises throughout and omits lengthy proofs, making the material accessible to students and practitioners.

Author Notes

Abhijit Das is an associate professor in the Department of Computer Science and Engineering at the Indian Institute of Technology, Kharagpur. His research interests are in the areas of arithmetic and algebraic computations with specific applications to cryptology.

Preface	p. xv
1 Arithmetic of Integers	p. 1
1.1 Basic Arithmetic Operations	p. 2
1.1.1 Representation of Big Integers	p. 3
1.1.1.1 Input and Output	p. 3
1.1.2 Schoolbook Arithmetic	p. 5
1.1.2.1 Addition	p. 5
1.1.2.2 Subtraction	p. 6
1.1.2.3 Multiplication	p. 7
1.1.2.4 Euclidean Division	p. 8
1.1.3 Fast Arithmetic	p. 11
1.1.3.1 Karatsuba-Ofman Multiplication	p. 11
1.1.3.2 Toom-Cook Multiplication	p. 13
1.1.3.3 FFT-Based Multiplication	p. 16
1.1.4 An Introduction to GP/PARI	p. 20
1.2 GCD	p. 27
1.2.1 Euclidean GCD Algorithm	p. 27
1.2.2 Extended GCD Algorithm	p. 29
1.2.3 Binary GCD Algorithm	p. 31
1.3 Congruences and Modular Arithmetic	p. 33
1.3.1 Modular Exponentiation	p. 38
1.3.2 Fast Modular Exponentiation	p. 39
1.4 Linear Congruences	p. 41
1.4.1 Chinese Remainder Theorem	p. 41
1.5 Polynomial Congruences	p. 44
1.5.1 Hensel Lifting	p. 44
1.6 Quadratic Congruences	p. 46
1.6.1 Quadratic Residues and Non-Residues	p. 47
1.6.2 Legendre Symbol	p. 47
1.6.3 Jacobi Symbol	p. 49
1.7 Multiplicative Orders	p. 51
1.7.1 Primitive Roots	p. 51
1.7.2 Computing Orders	p. 53
1.8 Continued Fractions	p. 54
1.8.1 Finite Continued Fractions	p. 54
1.8.2 Infinite Continued Fractions	p. 55
1.9 Prime Number Theorem and Riemann Hypothesis	p. 58
1.10 Running Times of Arithmetic Algorithms	p. 60
2 Arithmetic of Finite Fields	p. 75
2.1 Existence and Uniqueness of Finite Fields	p. 76
2.2 Representation of Finite Fields	p. 77
2.2.1 Polynomial-Basis Representation	p. 78
2.2.2 Working with Finite Fields in GP/PARI	p. 81
2.2.3 Choice of the Defining Polynomial	p. 83
2.3 Implementation of Finite Field Arithmetic	p. 84
2.3.1 Representation of Elements	p. 84
2.3.2 Polynomial Arithmetic	p. 86
2.3.2.1 Addition and Subtraction	p. 86
2.3.2.2 Multiplication	p. 87
2.3.2.3 Comb Methods	p. 88
2.3.2.4 Windowed Comb Methods	p. 90
2.3.2.5 Modular Reduction	p. 92
2.3.3 Polynomial GCD and Inverse	p. 94
2.3.3.1 Euclidean Inverse	p. 94
2.3.3.2 Binary Inverse	p. 95
2.3.3.3 Almost Inverse	p. 97
2.4 Some Properties of Finite Fields	p. 99
2.4.1 Fermat's Little Theorem for Finite Fields	p. 99
2.4.2 Multiplicative Orders of Elements in Finite Fields	p. 101
2.4.3 Normal Elements	p. 102
2.4.4 Minimal Polynomials	p. 103
2.4.5 Implementing Some Functions in GP/PARI	p. 106
2.5 Alternative Representations of Finite Fields	p. 108
2.5.1 Representation with Respect to Arbitrary Bases	p. 108
2.5.2 Normal and Optimal Normal Bases	p. 109
2.5.3 Discrete-Log Representation	p. 110
2.5.4 Representation with Towers of Extensions	p. 111
2.6 Computing Isomorphisms among Representations	p. 113
3 Arithmetic of Polynomials	p. 121
3.1 Polynomials over Finite Fields	p. 122
3.1.1 Polynomial Arithmetic	p. 122
3.1.2 Irreducible Polynomials over Finite Fields	p. 122
3.1.3 Testing Irreducibility of Polynomials	p. 125
3.1.4 Handling Irreducible Polynomials in GP/PARI	p. 127
3.2 Finding Roots of Polynomials over Finite Fields	p. 128
3.2.1 Algorithm for Fields of Odd Characteristics	p. 129
3.2.2 Algorithm for Fields of Characteristic Two	p. 131
3.2.3 Root Finding with GP/PARI	p. 132
3.3 Factoring Polynomials over Finite Fields	p. 133
3.3.1 Square-Free Factorization	p. 134
3.3.2 Distinct-Degree Factorization	p. 135
3.3.3 Equal-Degree Factorization	p. 136
3.3.4 Factoring Polynomials in GP/PARI	p. 142
3.4 Properties of Polynomials with Integer Coefficients	p. 145
3.4.1 Relation with Polynomials with Rational Coefficients	p. 145
3.4.2 Height, Resultant, and Discriminant	p. 147
3.4.3 Hensel Lifting	p. 151
3.5 Factoring Polynomials with Integer Coefficients	p. 154
3.5.1 Berlekamp's Factoring Algorithm	p. 154
3.5.2 Basis Reduction in Lattices	p. 160
3.5.3 Lenstra-Lenstra-Lovász Factoring Algorithm	p. 166
3.5.4 Factoring in GP/PARI	p. 169
4 Arithmetic of Elliptic Curves	p. 177
4.1 What Is an Elliptic Curve?	p. 178
4.2 Elliptic-Curve Group	p. 183
4.2.1 Handling Elliptic Curves in GP/PARI	p. 191
4.3 Elliptic Curves over Finite Fields	p. 194
4.4 Some Theory of Algebraic Curves	p. 199
4.4.1 Affine and Projective Curves	p. 199
4.4.1.1 Affine Curves	p. 199
4.4.1.2 Projective Curves	p. 200
4.4.2 Polynomial and Rational Functions on Curves	p. 205
4.4.3 Rational Maps and Endomorphisms on Elliptic Curves	p. 213
4.4.4 Divisors	p. 217
4.5 Pairing on Elliptic Curves	p. 222
4.5.1 Weil Pairing	p. 222
4.5.2 Miller's Algorithm	p. 223
4.5.3 Tate Pairing	p. 227
4.5.4 Non-Rational Homomorphisms	p. 232
4.5.4.1 Distortion Maps	p. 232
4.5.4.2 Twists	p. 233
4.5.5 Pairing-Friendly Curves	p. 234
4.5.6 Efficient Implementation	p. 236
4.5.6.1 Windowed Loop in Miller's Algorithm	p. 237
4.5.6.2 Final Exponentiation	p. 237
4.5.6.3 Denominator Elimination	p. 239
4.5.6.4 Loop Reduction	p. 240
4.6 Elliptic-Curve Point Counting	p. 243
4.6.1 A Baby-Step-Giant-Step (BSGS) Method	p. 244
4.6.1.1 Mestre's Improvement	p. 246
4.6.2 Schoof's Algorithm	p. 247
5 Primality Testing	p. 265
5.1 Introduction to Primality Testing	p. 266
5.1.1 Pratt Certificates	p. 266
5.1.2 Complexity of Primality Testing	p. 268
5.1.3 Sieve of Eratosthenes	p. 268
5.1.4 Generating Random Primes	p. 269
5.1.5 Handling Primes in the GP/PARI Calculator	p. 270
5.2 Probabilistic Primality Testing	p. 271
5.2.1 Fermat Test	p. 271
5.2.2 Solovay-Strassen Test	p. 274
5.2.3 Miller-Rabin Test	p. 275
5.2.4 Fibonacci Test	p. 277
5.2.5 Lucas Test	p. 280
5.2.6 Other Probabilistic Tests	p. 284
5.3 Deterministic Primality Testing	p. 284
5.3.1 Checking Perfect Powers	p. 285
5.3.2 AKS Test	p. 287
5.4 Primality Tests for Numbers of Special Forms	p. 289
5.4.1 Pépin Test for Fermat Numbers	p. 289
5.4.2 Lucas-Lehmer Test for Mersenne Numbers	p. 290
6 Integer Factorization	p. 297
6.1 Trial Division	p. 299
6.2 Pollard's Rho Method	p. 301
6.2.1 Floyd's Variant	p. 302
6.2.2 Block GCD Calculation	p. 304
6.2.3 Brent's Variant	p. 304
6.3 Pollard's p-1 Method	p. 306
6.3.1 Large Prime Variation	p. 309
6.4 Dixon's Method	p. 310
6.5 CFRAC Method	p. 316
6.6 Quadratic Sieve Method	p. 318
6.6.1 Sieving	p. 319
6.6.2 Incomplete Sieving	p. 323
6.6.3 Large Prime Variation	p. 324
6.6.4 Multiple-Polynomial Quadratic Sieve Method	p. 326
6.7 Cubic Sieve Method	p. 327
6.8 Elliptic Curve Method	p. 330
6.9 Number-Field Sieve Method	p. 335
7 Discrete Logarithms	p. 345
7.1 Square-Root Methods	p. 347
7.1.1 Shanks' Baby-Step-Giant-Step (BSGS) Method	p. 348
7.1.2 Pollard's Rho Method	p. 349
7.1.3 Pollard's Lambda Method	p. 350
7.1.4 Pohlig-Hellman Method	p. 351
7.2 Algorithms for Prime Fields	p. 352
7.2.1 Basic Index Calculus Method	p. 353
7.2.2 Linear Sieve Method (LSM)	p. 355
7.2.2.1 First Stage	p. 356
7.2.2.2 Sieving	p. 358
7.2.2.3 Running Time	p. 359
7.2.2.4 Second Stage	p. 359
7.2.3 Residue-List Sieve Method (RLSM)	p. 360
7.2.4 Gaussian Integer Method (GIM)	p. 363
7.2.5 Cubic Sieve Method (CSM)	p. 366
7.2.6 Number-Field Sieve Method (NFSM)	p. 369
7.3 Algorithms for Fields of Characteristic Two	p. 370
7.3.1 Basic Index Calculus Method	p. 371
7.3.1.1 A Faster Relation-Collection Strategy	p. 373
7.3.2 Linear Sieve Method (LSM)	p. 375
7.3.3 Cubic Sieve Method (CSM)	p. 378
7.3.4 Coppersmith's Method (CM)	p. 381
7.4 Algorithms for General Extension Fields	p. 384
7.4.1 A Basic Index Calculus Method	p. 384
7.4.2 Function-Field Sieve Method (FFSM)	p. 385
7.5 Algorithms for Elliptic Curves (ECDLP)	p. 386
7.5.1 MOV/Frey-Rück Reduction	p. 387
8 Large Sparse Linear Systems	p. 393
8.1 Structured Gaussian Elimination	p. 395
8.2 Lanczos Method	p. 404
8.3 Wiedemann Method	p. 410
8.4 Block Methods	p. 415
8.4.1 Block Lanczos Method	p. 415
8.4.2 Block Wiedemann Method	p. 421
9 Public-Key Cryptography	p. 429
9.1 Public-Key Encryption	p. 433
9.1.1 RSA Encryption	p. 433
9.1.2 ElGamal Encryption	p. 436
9.2 Key Agreement	p. 437
9.3 Digital Signatures	p. 438
9.3.1 RSA Signature	p. 438
9.3.2 ElGamal Signature	p. 439
9.3.3 DSA	p. 440
9.3.4 ECDSA	p. 441
9.4 Entity Authentication	p. 442
9.4.1 Simple Challenge-Response Schemes	p. 442
9.4.2 Zero-Knowledge Protocols	p. 444
9.5 Pairing-Based Cryptography	p. 447
9.5.1 Identity-Based Encryption	p. 449
9.5.1.1 Boneh-Franklin Identity-Based Encryption	p. 449
9.5.2 Key Agreement Based on Pairing	p. 452
9.5.2.1 Sakai-Ohgishi-Kasahara Two-Party Key Agreement	p. 452
9.5.2.2 Joux Three-Party Key Agreement	p. 453
9.5.3 Identity-Based Signature	p. 454
9.5.3.1 Shamir Scheme	p. 454
9.5.3.1 Paterson Scheme	p. 455
9.5.4 Boneh-Lynn-Shacham (BLS) Short Signature Scheme	p. 457
Appendices	p. 465
Appendix A Background	p. 467
A.1 Algorithms and Their Complexity	p. 467
A.1.1 Order Notations	p. 468
A.1.2 Recursive Algorithms	p. 471
A.1.3 Worst-Case and Average Complexity	p. 475
A.1.4 Complexity Classes P and NP	p. 479
A.1.5 Randomized Algorithms	p. 481
A.2 Discrete Algebraic Structures	p. 483
A.2.1 Functions and Operations	p. 483
A.2.2 Groups	p. 484
A.2.3 Rings and Fields	p. 488
A.2.4 Vector Spaces	p. 492
A.2.5 Polynomials	p. 494
A.3 Linear Algebra	p. 495
A.3.1 Linear Transformations and Matrices	p. 496
A.3.2 Gaussian Elimination	p. 497
A.3.3 Inverse and Determinant	p. 502
A.3.4 Rank and Nullspace	p. 506
A.3.5 Characteristic and Minimal Polynomials	p. 509
A.4 Probability	p. 510
A.4.1 Random Variables and Probability Distributions	p. 511
A.4.2 Birthday Paradox	p. 513
A.4.3 Random-Number Generators	p. 514
Appendix B Solutions to Selected Exercises	p. 517
Index	p. 583

Available:*

On Order

Summary

Summary

Author Notes

Table of Contents