Suugaku Girl supplementary handout for chapter 2: Prime numbers

She doesn't seem that excited

So last time, Tetra was being enlightened by MC-kun about definitions. This actually arises from MC-kun using prime numbers as a motivating example.

Primes are megas important in mathematics and even more important today. The entire branch of mathematics called number theory is all about studying the properties of prime numbers. They’re so useful that we’ve done stuff like extend the notion of prime elements to algebraic structures called rings or apply analytic techniques to learn more about them, but we’ll stick with elementary number theory for now.

Now, for hundreds of years, we’d been studying number theory only because it’s cool and mathematicians love prime numbers. Last time, I mentioned some examples of math preceding useful applications. Well, number theory is a really good example of that, because in the 70s, we found a use for it, which is its main use today, in cryptography. There have been some new techniques using some algebra as well, but for the most part, modern cryptography relies on the hardness of factoring primes. Neat!

Okay, so we’re back to the original question that MC-kun tries to get Tetra to answer, which is, what is a prime number?

Definition. An integer $p$ is prime if and only if $p\geq 2$ and the only positive divisors of $p$ are 1 and itself.

MC-kun explains that the motivation for excluding 1 from the definition of a prime number is because we want to be able to say that we can write every number as a unique product of prime numbers. This is very useful, because now we know we can break down every number like this and we can tell them apart because they’re guaranteed to have a unique representation. This is called unique prime factorization.

Theorem. Let $a > 0$ be an integer. Then we can write $a = p_1p_2\cdots p_k$ for some primes $p_1,\dots,p_k$. This representation is unique up to changing the order of terms.

We can show this by induction on $a$. We’ve got $a=2$ so that’s pretty obvious. So let’s say that every integer $k\lt a$ can be decomposed like this and suppose we can’t decompose $a$ into prime numbers, assuming $a$ itself isn’t already a prime since it would just be its own prime decomposition. Then we can factor $a=cd$ for some integers $c$ and $d$. But both $c$ and $d$ are less than $a$, which means they can be written as a product of primes, so we just split them up into their primes and multiply them all together to get $a$. Tada.

As a sort of side note, I mentioned before that primes are so useful that we wanted to be able to extend the idea of prime elements into rings. Well, it turns out for certain rings, it isn’t necessarily true that numbers will always have a unique representation when decomposed into primes. This is something that comes up in algebraic number theory, which is named so because it involves algebraic structures and techniques. This was invented while we were trying to figure out if Fermat’s Last Theorem was actually true (which needed this and other fun mathematical inventions from the last century that implies that Fermat was full of shit when he said he had a proof).

So at the end of the chapter, after Tetra gets her chair kicked over by the megane math girl, we’re treated to a note that acts as a sort of coda to the chapter that mentions that there are infinitely many primes. How do we know this?

Suppose that there are only finitely many primes. Then we can just list all of the prime numbers, like on Wikipedia or something. So we’ve got our list of primes $p_1,p_2,\dots,p_k$. So let’s make a number like $N=1+p_1\cdots p_k$. Well, that number is just a regular old number, so we can break it down into its prime factors. We already know all the primes, so it has to be divisible by one of them, let’s say $p_i$.

Now we want to consider the greatest common divisor of the two numbers, which is just the largest number that divides both of them. We’ll denote this by $\gcd(a,b)$. So since $p_i$ is a factor of $N$, we’ve got $\gcd(N,p_i)=p_i$. But then that gives us $p_i=\gcd(N,p_i)=\gcd(p_i,1)=1$ by a lemma that says that for $a=qb+r$, we have $\gcd(a,b)=\gcd(b,r)$. This means that we have $p_i=1$, which is a contradiction, since 1 isn’t a prime number, and so I guess there are actually infinitely many primes.

So the nice thing is that we won’t run out of prime numbers anytime soon, which is very useful because as we get more and more computing power, we’ll have to increase the size of the keys we use in our cryptosystems. Luckily, because factoring is so hard, we don’t need to increase that size very much before we’re safe for a while. Or at least until we develop practical quantum computers.

The (1st annual?) π day anime and mathematics lecture

Happy $\pi$ day. We’ll begin with an obligatory video.

One of the reasons I enjoyed Summer Wars so much is because the main character’s superpower is math. Well, okay, you say, he’s really good at math, but so what? A lot of people complain about the implausibility of OZ, but those of us with a basic understanding of cryptography and number theory will have been drawn to Kenji’s quick problem solving work with an eyebrow raised. So let’s talk about why Kenji is a wizard.

Kenji doing some friggin mathematics

Kenji doing some friggin mathematics

We’ll start with modular arithmetic, which Kenji mentions to Natsuki on the train ride to Ueda. When we divide numbers, we often end up with remainders. Suppose we divide some integer $k$ by $N$ and we get a remainder of $r$. Then we say that $k$ and $r$ are equivalent $\bmod{N}$ and we denote that by $k = r \bmod{N}$. Because it’s how division works, for any integer $k, r$ will be some number from $0$ to $N-1$. It turns out a lot of arithmetic operations work the same way in modular arithmetic: adding, subtracting, and multiplying numbers and then taking the modulus of the result will give you the same number as adding, subtracting, and multiplying the moduli of the numbers you started out with.

However, division doesn’t work as we would expect it to. So we have to think about division (or the equivalent operation) differently. Instead of thinking of division as splitting a group of stuff into smaller groups, we’ll think of it as multiplying by an inverse. What’s an inverse? Well, we can try thinking of it in terms of addition. It’s pretty intuitive that subtraction is the opposite of addition. If we have some integer $k$, then the additive inverse of $k$ is $-k$. When we add $k$ and $-k$, we get $0$, the additive identity. The identity is just the special number that we can add to anything and get that same thing back unchanged ($n+0 = n$). In the same way, if we multiply $k$ by its inverse, $k^{-1}$, then we’ll get $1$, since $k \times 1$ is just $k$ again. What this means is that the inverse of $k \bmod{N}$ is just some other number $j$ from $0$ to $N-1$ such that $j\cdot k = 1 \bmod{N}$ and it’s just multiplication again.

Now, the problem with this is that it’s not guaranteed that there’s always an inverse hanging around in $\bmod{N}$. In particular, if $k$ and $N$ share any divisors, then $k$ won’t have an inverse $\bmod{N}$. This is interesting because it also tells us that if we consider integers mod a prime number $P$, then every integer $\bmod{P}$ has an inverse, since $P$ doesn’t share any divisors with any integers from $0$ to $P-1$. We call these things that have inverses units. So if we have a unit $k$, then $k^m$ is also a unit, for any integer $m$. We even have a funny function $\phi$ defined such that $\phi(n)$ is the number of units in $\bmod{n}$.

Love Machine solicits help

Love Machine solicits help

So taking everything we’ve learned, we can set up a cryptosystem! The one we’ll be looking at is called RSA, after the guys who invented it. We have Bob who wants to securely send a message $M$ to Alice. Alice chooses two prime numbers $p$ and $q$ and figures out $m = pq$. She also goes and figures out $\phi(m)$, which happens to be $(p-1)(q-1)$. Finally, she picks some integer $k$, a unit in $\bmod{\phi(m)}$. She lets everyone know $m$ and $k$, but she keeps $p$, $q$, and $\phi(m)$ secret.

So Bob wants to send $M$, which is just his message conveniently in number form. He makes $M$ into a number between $0$ and $m$, and if $M$ is too big, he can just break it up into chunks. Bob figures out the smallest $b$ such that $b = a^k \bmod{m}$ and sends $b$ over to Alice. Now, since Alice has $k$ and $\phi(m)$, she can also find $k^{-1}$ pretty easily. Once she has that, she can get the original message by figuring out $b^{k^{-1}} = (M^k)^{k{-1}} = M \bmod{m}$, since $kk^{-1} = 1 \bmod \phi(m)$.

The interesting thing here is that all of the information is out there for someone to encrypt a message to send to Alice, but no one is able to decrypt it. Well, they’re able to decrypt it if they know what $p$ and $q$ are, since once they’ve got that, they can get $\phi(m)$. But it turns out getting $p$ and $q$ from $m$ (which Alice just throws up on the interwebs) is really hard. And it really works for reals, because RSA is pretty widely deployed for things like keeping your credit card information safe while you send it through the tubes to Amazon.

A conveniently displayed ciphertext

A conveniently displayed ciphertext

Let’s go back and think about units some more. Of course, there are only $N$ numbers in the integers $\bmod{N}$, so there’s a point at which $k^m$ is just $1$ again and starts over. If $k^m = 1 \bmod{N}$, we say that $m$ is the order of $k$. But why do we care about finding the order of $k$?

It turns out finding the order of elements is very, very similar to factoring an integer into primes and other related problems, like discrete logarithms. If we can find orders of elements, it won’t be too hard to figure out how to factor a number. In this case, the eavesdropper wants to figure out what $p$ and $q$ are, so they’ll want to factor $m$. And it turns out a lot of other public-key cryptosystems (like elliptic curves) are based on the difficulty of factoring.

How hard could it be? Well, we could just check every possibility, which doesn’t seem that bad for a number like 48, but once we get into numbers that are hundreds of digits long, that might start to suck. It turns out the fastest known algorithms for order finding take approximately $e^{O(\log N \log \log N)^{\frac{1}{2}}}$ steps. Current key lengths for RSA are at least 1024 bits, which would give us about 4.4 x 1029 operations. Assuming three trillion operations per second (3 GHz), it’d take a PC about 4.7 billion years. Sure, you could just throw more powerful computers at it, but they’d just double the key size and suddenly, you’d need to do 1044 operations.

It's a lot easier to write math than typeset it

It's a lot easier to write math than typeset it

Well, that’s not entirely true. One of the breakthroughs in quantum computing was coming up with a fast algorithm for factoring. It turns out quantum order finding takes $O((\log N)^2 \log \log N \log \log \log N)$ steps, which, for a 1024-bit key is just over 60 operations. Doubling the key-size to 2048 bits only increases the number of operations by just over 20. Unfortunately (or fortunately, because we’d be pretty screwed if someone could easily break RSA right now), we haven’t built any quantum computers that large yet, nor are we capable of doing so anytime soon.

tl;dr – Kenji is a quantum computer.