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 )?
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?