Number Theory: Lecture 23

In which we encounter some methods for factorising a large number.

• Description of Fermat factorisation.
• Definition of least absolute residue.  (See also Gauss’s lemma, in lecture 7.)
• Definition of a factor base and of a -number.
• Description of the factor-base method.

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?

Advertisement