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

Then I choose an exponent to raise my secret message to...

I haven't told you \(\phi(n)\), but this guarantees it is coprime to my (public) encryption key \(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.

In fact, if we knew \(p\) and \(q\), we could easily calculate \(\phi(n)\) without even using Sage. Can you quickly now factor \(n\) without using Sage?

By the way, how would one be smart about it? Think strategically; how should I have chosen a public modulus \(n\) to make this hard to do? How should \(p\) and \(q\) relate?

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.

Okay, that was fun - but now, back to business.

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 the last class.” 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 a little different with \(n=899\) from our earlier RSA problem. 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 - 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.

• Write \(n=ab\), with \(a>b\), and assume \(n\) is odd (for hopefully obvious reasons!).
• Then we can write \(n\) as a difference of two square numbers.
• Namely, the squares of \(s=\frac{a+b}{2}\) and \(t=\frac{a-b}{2}\): \[s^2-t^2=\left(\frac{a+b}{2}\right)^2-\left(\frac{a-b}{2}\right)^2=\frac{a^2}{2}-\frac{a^2}{2}+\frac{b^2}{2}-\frac{b^2}{2}+\frac{2ab}{4}+\frac{2ab}{4}=ab=n\]

This may seem like an obscure identity to us, but at the time (and even until 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\).