Math 480, Spring 2015, Assignment 11

Carefully define the following terms, then give one example and one non-example of each:

1. $B$-smooth number.
2. Factor base.

Carefully describe the following algorithms:

1. Trial division (for finding a factor of an integer $n$).
2. Fermat's method (for finding a factor of an integer $n$).
3. Dickson's method (for finding a factor of an integer $n$).

Carefully state the following theorems (you do not need to prove them):

1. Time and memory complexity of trial division.
2. Time and memory complexity of Fermat's method.

Solve the following problems:

1. Problems 3.23(a-b), and 3.25(a-b).

--------------------End of assignment--------------------