*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*-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 -numbers (for a suitable factor base )?

#### Further reading

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 and suitable -numbers. How could continued fractions help us with this?

Advertisements

December 4, 2013 at 11:44 am

[…] Expositions of interesting mathematical results « Number Theory: Lecture 23 […]