Season 8 Episode 0

At the start of the previous season, we talked about how 91 is not a prime number. But how can you tell? In this episode, we'll factorise some numbers!

Further Reading

Quadratic Sieve

The quadratic sieve algorithm is described in (much) more detail here.

There’s a step that’s a little misleading in the Wikipedia page; the page says at one point "we can then factor 1649=gcd(194,1649)gcd(34,1649)". This step doesn’t necessarily follow from what we have on the previous line. In general, we're hoping that those greatest common divisors are the factorisation, but it’s possible that they’re not. I first learnt about it in the Oxford Mathematics Part A short option Number Theory lecture notes.

RSA-129

The very large number at the start of the stream is called RSA-129. You can read about it here.

I misspoke slightly on the stream – RSA-129 was not part of the RSA Factoring Challenge issued by RSA Laboratories. It was set as a separate RSA Challenge by Martin Gardner back in 1977. There's a description of the effort to factorise the number here, with an enigmatic title; The Magic Words are Squeamish Ossifrage.

Make a perfect square

Find a non-empty subset of the following four numbers which multiply together to give a square number.
$$30, 150, 12, 10.$$

(Harder) Prove that if four numbers have no prime factors other than 2 or 3 or 5, then there is a non-empty subset of those numbers which multiply together to give a square number.
(Harder) Prove that if \(n+1\) numbers have just \(n\) distinct prime factors between them, then there is a non-empty subset of those numbers which multiply together to give a square number.

Highest Common Factor

I said that I would give you a link for Euclid’s Algorithm.

Perhaps it’s surprising that “find any non-trivial factor of this composite number” is usually rather hard, while “find the largest number that’s a factor of both of these two numbers” is usually rather easy. You might think that you need to be able to do the first thing in order to do the second thing, but you don’t.

Follow-up question! This suggests a factorisation technique where we multiply together all the primes less than \(n\) and solve the “easy” problem of finding the largest number that’s a factor of both that product and \(n\). Why isn’t this a good idea?

While I was trying to give an overview of the algorithm, I mentioned Al-Khwarizmi. This was a well-meaning attempt to get some history of mathematics into the livestream, but I was way off the mark with my dates; I think I said that Al-Khwarizmi knew this algorithm before Euclid, but that’s impossible! Al-Khwarizmi is still worth reading about though. We get the word algorithm from his name. That's maybe why I was thinking of him.

A Tale of Two Sieves

The Quadratic Sieve was developed by Carl Pomerance, and they've written a great overview article on the method. It’s 13 pages, and even just the first four pages give you a good bit of context. Get it here; A Tale of Two Sieves.