## Number Theory: Lecture 23

In which we think about how to find a factor of a large number.

• Description of Fermat factorisation.
• Definition of a factor base and a $B$-number.
• Description of the factor base method.

#### Understanding today’s lecture

You could pick some large composite numbers and test these techniques on them.  Does Fermat factorisation find a factor quickly?  Can you find a number for which it works quickly and a number for which it works but only very slowly?  Can you find a good bunch of $B$-numbers (for a suitable factor base $B$)?

Koblitz (A Course in Number Theory and Cryptography) and recent editions of Davenport (The Higher Arithmetic) both cover this material nicely.

#### Preparation for Lecture 24

As we saw, the factor-base method relies on coming up with a suitable factor base $B$ and suitable $B$-numbers.  How could continued fractions help us with this?