Getting Primed For Halloween

Maybe it’s the chill in the air or the changing leaves, maybe it’s the ache in my belly from too much candy corn, but whatever the reason, I’ve been in the mood for spooky halloween things this past week. I’ve found my lectures veering towards the creepy — as creepy as a lecture on related rates can really be — and this week I was reminded of the most righteous marriage of math and the macabre: Cube.

A math major factors large numbers like her life depends on it, in this low-budget thriller.

This is quite easily the best low-budget Canadian horror movie to come out of the last millennium, truly thrilling. As a quick synopsis, a group of strangers wake up trapped in a cube. The cube has trapdoors on each face, on each trapdoor has a serial number consisting of a sequence of three-digit numbers. Through each trapdoor is another cube, and the film follows these strangers as they stumble from cube to cube. They quickly realize that some seemingly random cubes are booby-trapped with tripwires and acid. Luckily they have a math major in the cube with them (and hey, who doesn’t want a math major around during a tense situation?) and she realizes that as long as there are no prime numbers in the serial sequence, it’s safe to pass to the next cube. She starts to do rapid factorization in her head and deducing that the sequence 645, 372, 649 contains no primes, jumps through to a safe cube, and mouth agape, throws her head back in relief shouting, “PRIME NUMBERS! PRIME NUMBERS!” (much like I do most afternoons in the privacy of my study.)

The young math major at one point freaks out, saying that factoring large numbers is an “astronomical” task, one that she can’t possibly do in her head! While this is technically a true statement, in the world of primes, anything with less than 6 digits really doesn’t count as large. In fact, some of our most secure modern encryption is based purely on the fact that really big numbers are hard to factor. Nevertheless, it made me wonder. If I were trapped in a cube, and the responsibility fell onto my humble shoulders to find the primes, what are the smartest algorithms I could use to factor things?

Suppose we’re looking to factor a number N. First, there’s the classical check-all-numbers-and-see-if-they-divide-N method. Since you really only need to check up to √N, this method isn’t terrible for small values of N.

A similary efficient method is Fermat’s Factorization Method, which relies on the fact that any odd number can be written as a difference of squares. So if we can manage to write N as

N=a²-b²=(a+b)(a-b)

then we could reframe our quest for factors to the quest for suitable a and b. This method on its own isn’t much better than the old check-all-the-numbers method, but some combination of the two gives you a marginal improvement in efficiency.

Assuming N has at least one smallish prime factor, Pollard’s rho algorithm should give an improvement over the previous two methods. For larger numbers there are sieve methods. Carl Pomerance explains in the Notices of the AMS, “In 1990 my own quadratic sieve factoring algorithm had doubled the length of the numbers that could be factored, the record having 116 digits.”

The hardest numbers to factor are semiprimes — these are numbers which are products of two (not necessarily distinct) primes — which are the product of two really huge primes. To date, the largest one to be factored by computer was 232 digits long. A group did it by running a whole bunch of processors in parallel, but if you measured it in single CPU time, it would have taken 2000 years! Just so you can get a sense of what 232 digits looks like, here is the number:

12301866845301177551304949583849627207728535695953347921973224521517264005
07263657518745202199786469389956474942774063845925192557326303453731548268
50791702612214291346167042921431160222124047927473779408066535141959745985
6902143413

Spooky, huh?