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!"

Robert A. Heinlein, Have Space Suit---Will Travel

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



results matching ""

    No results matching ""