Let's look at another toy RSA problem to get a sense of what is going on. First, I choose a modulus \(n=899\). I will also use Sage to verify it has two prime factors, without telling you what they are.

Then I choose an exponent to raise my secret message by …

I haven't told you \(\phi(n)\), but this guarantees it is coprime to my (public) encryption key, which I have chosen to be \(e=13\). Now we can encode our message, \(x=11\).

Now, how could we hope to crack this sinister message? (Assume that euler_phi(899) is just too huge for Sage to do.) Well, we do know \(n=899\) and that \(e=13\). That could help. Remember, if we knew \(p\) and \(q\), we could easily calculate \(\phi(n)\) without even using Sage, which should be enough.

Hopefully you figured out \(p\) and \(q\). Then we just need to find an inverse modulo \(\phi(n)=(p-1)(q-1)\) to get our decryption key.

This simple example makes it clear why factorization, not just looking for primes, might be important. To be truthful, many researchers in factorization simply do it to stay one step ahead of the other side, who is presumably also researching factorization – so to some extent it is an arms race.

But factorization is also inherently interesting mathematically! Here is an interesting statement, as an example.

The first, and oldest, method of factoring is one you already know, and maybe used a few minutes ago – trial factorization. It is the method we used with the Sieve of Eratosthenes; you just try each prime number, one by one.

Do you remember what the highest number you would have to try in order to factor \(n\) by trial division is? (Can you prove it?)

The following algorithm does this very naively (and slowly, even for trial division). Let's try to talk through what each step does.

Now let me verify it works on easy examples. Remember, we are just looking for factors at this point, not complete factorizations.

Okay, so this seems reasonable. But it's a little more problematic when you try to do large numbers, where large means “bigger than you can do by hand, but nowhere close to the size we looked at in general.” I'll actually time how long it takes.

Sage actually has this implemented in a much faster way, primarily by using optimized integers and a special version of Python that allows turning it into much faster code in the C language (Cython). Notice that it just returns a single factor – another slight speedup.

That's roughly one thousand times faster for the initial example! Naturally, it's possible to speed up even more. But note that getting the full factorization slows us back down; after all, one has to check that the remaining factor is prime (or factor it, if it isn't).

Even for this smaller number it takes some actual time – here is where one sees the difference between different implementations of the same algorithm.

So much for trial division! But we have other tools at our disposal.

Some of you might have tried something other than straight trial factorization when attacking \(n=899\) from our earlier problem. Reason this way; since we know that someone is trying to protect a secret, they probably are not going to pick a number with primes like \(3\) and \(5\) in it. After all, that would be too easy to factor.

In fact, it stands to reason that the primes \(p\) and \(q\) should be relatively large compared to \(n\) – so why not start in the middle?

This was Fermat's idea for factoring larger numbers. However, he didn't just start with primes in the middle; for one thing, if your number is even somewhat big and you don't have a computer or huge list of primes, how would you know where to start? So Fermat became clever, as always, and used an algebraic identity to help himself along.

This may seem like an obscure identity to us, but at the time (and even well into the last century) such identities were the bread and butter of algebra, before we had tools like computers to help us along.

So what Fermat did is to try this identity backwards. Here is his strategy.

Here is an implementation – again, assuredly slow, but at least verbose in its explanation – of this strategy. We simply start with the next \(s\) above the square root of \(n\), and just keep trying \(s^2-n\) again and again for bigger and bigger \(s\).