The Bourne Factor
The search for a factoring algorithm
Matt Damon is one of Hollywood’s iconic actors. His career was launched as both actor and screenwriter in the movie Good Will Hunting, in which he played a janitor who solves open problems in algebraic graph theory that are posed by a Fields Medal-winning MIT professor. He is recently known for playing Jason Bourne in movies The Bourne Identity, The Bourne Supremacy, and The Bourne Ultimatum based on Robert Ludlum’s thriller novels. The next movie in the series, The Bourne Legacy, does not have Matt Damon and does not have the Jason Bourne character. So where are Damon and Bourne?
Today Ken and I would like to discuss The Bourne Factor, the movie and its plot.
Why haven’t you heard about a movie called The Bourne Factor? Besides starring Damon once again as Jason Bourne, it has Kate Beckinsale as his love interest, and Helen Mirren as their powerful adversary. Why rush out in its place a non-Bourne Bourne movie sans Damon, and with a different director? I wonder if the real-life story of The Bourne Factor may have become a bit too real-life…
The problem is that the movie is based on the problem. Not . The problem is always the factoring of integers. Always. As you might imagine it is exciting to see a movie based on one of my favorite problems—it has been so long since Sneakers. Len Adleman made sure the equations filling blackboards in the opening scenes of Sneakers were real and about factoring. Damon undoubtedly wanted up-to-date equations. But what if he or someone else on the set found a new way to solve one of them?
The Plot—Spoiler Alert
As I said the plot plays out in real life. In real life…
The story starts when a graduate student, played by Brie Larson, discovers, almost by accident, a new fact about integers. Brie gives her paper explaining it to her bored professor, played by Beckinsale, at the end of a class. That night Beckinsale cannot sleep, so she decides to glance at the paper. Kate expected it to be wrong, but realizes it is correct, and that Brie has made a major discovery. Not only this, she realizes that the discovery can be used to factor integers—and thereby break RSA. She e-mails Brie congratulating her on the breakthrough, and suggests they meet in the morning at Starbuck’s.
Beckinsale is stood up, and after finally giving up and starting to go to her office, she decides to stop by Brie’s dorm. Kate finds Brie’s door unlocked, enters her room, and discovers that Brie has been killed in a horrible manner and her laptop stolen. She calls 911, but something scares her and she leaves before finishing the call.
An attempt on Kate’s life forces her to go on the run. She is actually—unknown to her—running from two groups. One group wants the secret, while the other group, Mirren’s people, seems only to want the secret destroyed. Damon enters the movie as Beckinsale’s ex-boyfriend, who at first does not understand why anyone would care about Kate’s secret. But when she is almost killed by a sniper through a computer lab window, he reluctantly agrees to help her get to safety.
There is a very unusual car chase—I will not spill the details here but it has to do with hijacking communications between self-guiding cars. There are many near misses and surprises as the movie unfolds, with government agents seeming to be on all three sides. There is a twist when Beckinsale is kidnapped by Mirren and Damon has to rescue her before a certain test related to David Deutsch’s explanation of how quantum computers work is carried out on her…
Okay I am just dreaming. I think we could write such a script, and it would be a cool movie. But what I would like today is to discuss what we know about factoring and what we do not know. In the brilliant 1993 HBO movie And the Band Played On about the start of the AIDS epidemic one of the discussions at CDC starts:
Dr. Jim Curran: All right, what do we think? What do we know? What can we prove?
Most think that integer factoring is computationally hard—in particular, that factoring sufficiently large that are the product of two randomly selected large primes is hard. It is critical that this problem not just be hard in worst case, but that it is hard in this strong sense: Pick two random and randomly in a large enough range, then given , finding and is hard in all but a vanishing fraction of cases.
Note that for even “harder” problems such as , generating hard instances is quite non-trivial. And even more, it appears for that all kinds of randomly generated instances may actually be easy. Certainly one must use great care in generating sets of clauses to make them hard: too few clauses are easy and too many are easy. What makes factoring so useful for cryptography is that it appears to be very easy to generate random hard instances.
It is important to have hardness for a great many instances. The unwelcome clustering of RSA keys currently in use that was found in the paper by Arjen Lenstra and others may owe at least in part to unwitting repetition in the selection of primes and based on too-simple use of pseudo-random number generators.
We do know that it is unlikely that factoring is very hard, that it is -complete for example. This is because factoring lies in , and because factoring has quite good algorithms such as the famous Number Field Sieve.
We also know that there is a quantum polynomial time algorithm for factoring due to Peter Shor. Many use this to argue that quantum is more powerful than classic algorithms. Yet, if there were a sufficiently good simulation of Shor’s algorithm, then factoring would be easy. We have just discussed this in a recent post—see here.
But it a real sense for all we know factoring could have a linear time algorithm. This may be of low probability but it is possible.
There is another thread that I have worked on, for years, to understand factoring. Suppose factoring is indeed hard, then what are the consequences of this assumption? Not consequences like “we can build a secure cryptosystem,” but consequences in other parts of mathematics. For example, consider equations of the form
where is polynomial in and , and are numbers with only polynomial in bits. Note that the number of bits in the left hand side is exponential in , but the right hand size also has exponential in bits—so no trivial size-based argument will destroy the possibility that such an identity is true. If it is true in general, then factoring has polynomial size circuits. Even better, can be replaced by a number that has many factors. Thus the hardness of factoring would show at a sweep that certain kinds of equation Pierre de Fermat might have written in his margins are unsolvable.
This is even more concrete than the connection found in the famous “Natural Proofs” work of Alexander Razborov and Stephen Rudich. They proved that if factoring is hard in the strongest possible senses, than there cannot be certain kinds of proofs that —or any other similar problem—lacks polynomial-size circuits.
Would you like to see another movie on this subject? Could it actually work? Perhaps I will take the summer off and try to write a screenplay. If you are an agent please give me a call at 555-385-1212.