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

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

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

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 10²⁹ 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 10⁴⁴ operations.

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.

is amazing.

Summer Wars was on my list of things to look out for. The first promo pictures were intriguing, with Natsuki standing in front of her family. And then the first trailers came out and that shot my anticipation up by about 2000%. In hit theatres in August and sadly, there still hasn’t been any news of a DVD/BRD release. Luckily enough, a terrible Korean-hardsubbed raw showed up on the Internets. I debated for a while whether or not to wait it out, but impatience and people going crazy over this movie won me over.

Let’s start out with the first and coolest thing we’re introduced to: OZ. OZ is essentially a much, much cooler Second Life that is actually useful beyond flying around. Every possible thing that you could think of is tied to OZ: GPS systems, utilities, emergency services, commerce, entertainment, everything. As someone who understands software design, this super-centralized system is frightening.

Now, Natsuki mentions that she’s born in 1992 and she’s 18, which sets Summer Wars in next year. I guess that’s why we’re seeing Windows 7 and DSes connect to OZ. Again, I find it frightening that someone imagined that every aspect of our lives would be intricately tied to Second Life by next year. The movie’s main plot thread starts when OZ’s security (which is apparently a 2056 digit number) is broken and an AI starts taking over. Obviously, because everything is tied to OZ, the real world is essentially thrown into chaos.

So who do we have to save the day? Mild-mannered math nerd Koiso Kenji. How does he get roped into saving the world? By getting conned by his crush, Shinohara Natsuki. Basically, she wants him to pretend to be her fiancee at her grandmother’s ninetieth birthday, where her entire extended family will be gathered.

Being the unconfident guy that he is, Kenji doesn’t really do much saving at first. Much of that glory falls to Grandma, who might be the most awesome character in the movie. She demonstrates her power and her sense of responsibility, using her vast connections in the midst of the OZ crisis and by not taking any crap from one of her kids. At the same time, she’s not crazy like the head of the Sonozaki family. Her priority is her family and she’s the central figure to that family.

That family is pleasantly diverse. Unlike your standard powerful anime families, this family has members everywhere. They’re civil servants or rescue workers or businessmen or fishermen. They’ve got housewives, kids, and young adults. And what’s great about the movie is that the interactions between the family and with Kenji feel very real. Yeah, those are those annoying aunts and those cousins that you meet up with every year.

Now, honestly, Kenji doesn’t really do that much saving. I mean, he’s good at math, but the only useful thing that seems to come out of that is only factoring 2056 digit numbers on paper. He really doesn’t even do much in OZ. What he is able to do indirectly is move the rest of the family into action. He starts off very unconfident of himself, but grows through his time with this rambunctious family to the point where he’s able to take a stand for fighting this thing and by the end, does end up saving the day through math.

There’s a ton of good stuff that’s explored here. We’ve got the whole technology angle with OZ. We’ve got all of the family stuff going on. We’ve got a bunch of characters that are unsure of themselves who grow throughout the movie. And of course, there’s a budding romance that needs some growing.

One of the things that I really liked from this movie was the fact that it had so much stuff that happened in it. Usually, I prefer TV series because I find they have more time to develop their characters and carry out more elaborate plots. Summer Wars was able to have a lot of discrete events and still have it paced really naturally. I’m surprisingly satisfied with how much the movie covered.

And the visuals! Madhouse is a pretty amazing studio. Most of the movie looks like The Girl Who Leapt Through Time stuff, which is to be expected. And those parts look great. But the real eye candy is in the OZ scenes. That stuff is worth watching in Blu-ray. OZ is ridiculously detailed. There are a ridiculous number of objects in OZ and they all look great.

I’m pretty sure there’s a ton of stuff I missed out while throwing this post together, but basically, tl;dr: Summer Wars is probably the best animated work of this year.