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

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

One Response to “Number Theory: Lecture 23”

  1. Number Theory: Lecture 24 | Theorem of the week Says:

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

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: