Chapter 2.8 --- Extra Credit
"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.
Prime Numbers, Revisited
Alternate Approaches to Factorization
Factorizing Primes with Look-up Tables
Factorizing Primes with Pollard's Rho Algorithm
Factorizing Primes with Lenstra's Elliptical Curve
Factorizing Primes with the Quadratic Sieve
Factorizing Primes with the General Number Field Sieve
Automatic Factorization Algorithm Selection
Even More Polynomials
More Modular Exponentiation
The Jacobi Function
The Euler Totient Function
The Carmichael Functions
More Carmichael Functions
Even More Carmichael Functions
Optimizing for Performance
Optimizing for Memory Use
Putting It All Together