# 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**

```
```