Chapter 2.8 --- Extra Credit

Number Theory

"Some people insist that 'mediocre' is better than 'best.' They delight in clipping wings because they themselves can't fly. They despise brains because they have none. Pfah!"

Number Theory is a fun, but challenging domain for computer scientists---many aspects of it pose intractable problems for classical computation, forcing us to look to novel technologies for solutions, such as Quantum Computation. But in the age of concurrency, there are some minor tweaks and adjustments that can be made to the established algorithms, so that while we still cannot efficiently factorize the multiplication of two large primes, we can at least push classical computing to its absolute limit.

Through the excercises in this chapter, we will put together a Number Theory library that can be included in other projects, and contains a number of useful techniques for algorithm design, optimization, unit testing, and further develops on the iterative, incremental development pattern encouraged in Lisp. We will approach each problem from its theoretical ideal, and then work towards a computational ideal that is as efficient as possible while retaining elegance in expression.

Exercise 2.8.1

Prime Numbers, Revisited

Exercise 2.8.2

Alternate Approaches to Factorization

Exercise 2.8.3

Factorizing Primes with Look-up Tables

Exercise 2.8.4

Factorizing Primes with Pollard's Rho Algorithm

Exercise 2.8.5

Factorizing Primes with Lenstra's Elliptical Curve

Exercise 2.8.6

Factorizing Primes with the Quadratic Sieve

Exercise 2.8.7

Factorizing Primes with the General Number Field Sieve

Exercise 2.8.8

Automatic Factorization Algorithm Selection

Exercise 2.8.9

Polynomials

Exercise 2.8.10

More Polynomials

Exercise 2.8.11

Even More Polynomials

Exercise 2.8.12

Modular Exponentiation

Exercise 2.8.13

More Modular Exponentiation

Exercise 2.8.14

Inverse Modulus

Exercise 2.8.15

The Jacobi Function

Exercise 2.8.16

The Euler Totient Function

Exercise 2.8.17

The Carmichael Functions

Exercise 2.8.18

More Carmichael Functions

Exercise 2.8.19

Even More Carmichael Functions

Exercise 2.8.20

Optimizing for Performance

Exercise 2.8.21

Optimizing for Memory Use

Exercise 2.8.22

Putting It All Together