This was the last episode of the series. Overall, "Prime Target" was nice to watch despite (as critics
rightly pointed out) "sludgy pacing" or "isn't consistent of its own universe" (on IMDB).
The whole series would have made a nice feature movie or mini-series. For a TV series with 8 episodes, the plot
was simply too thin. They tried to build in the Baghdad subplot but that did not quite
make sense. The length however allowed the writers to include quite a bit
of math content. They definitely should have consulted a bit more with
cryptologists. The story claims that the math student Edward Brooks
cracks public key cryptography and hints at some points to the
Wilson theorem characterizing primes as number for which (n-1)!+1 is
divisible by n. Public key cryptography is based on two difficulties
which are related: to factor large integers and to solve the discrete
log problems in finite groups. The later both would attack RSA and Diffie-Hellman).
The 2012 movie
Travelling Salesman definitely had better math consultants
for the movie. "Travelling Salesman" also hallucinates of some
group of mathematicians solving an P-NP complete problem.
Also Sneakers 1992
was smarter by actually asking Adelman (the A in RSA) to consult and there is a nice reference to
realistic factoring algorithms in number fields.
A bit more realism would have been helpful also in "Prime Target". Rather than suggesting links
to the House of Wisdom which does not fit
(Al Khwarizmi was solving the quadratic equation but did not have "zero" nor negative numbers yet,
Al khwarizmi was also not researching substantially on prime numbers as far as we know), one could
have pushed a bit more realistic ideas on how to attack the fundamental problems in modern cryptology.
When I was in the Swiss military cryptology group,
Ueli Maurer had been the "brain"
of the group. He at that time also made progress in understanding the
significance of the discrete log problem, Maurer proved some connections. I'm sure he might have had
better suggestions about possible attacks of public key cryptosystems.
The mathematics of public key cryptology is quite simple: in any finite Abelian group G there is naturally an exponential map
expa(n) = a*a*....*a = an. It is an empirical fact that solving
the equation ax = y for x is hard in large groups like G=Zp where p is a large
prime or in a large elliptic curve. Finding the solution x = loga(y) is the discrete log problem.
This, as well as factoring are the key problem and not (as the movie suggests, to find formulas for large primes).
By the way, I myself as a dynamical systems person like to think about this as follows. You have a dynamical
system T: G -> G an initial point x in G and a target set Y in G. The question is how how long
do you have to wait to reach Y? [In the solar system one could ask for example, how long does one
has to wait until the earth collides with mars, using the usual dynamics (relativistically corrected
Newtonian dynamics). One knows that it does not happen in billions of years (numerical computations
show a rather strong KAM stability of the orbits) but it is not excluded mathematically that after
10l00 years such a collision occurs provided the celestial bodies would remain intact of
course. This is quite a good analogy because also in the discrete log problem, the solution n is not
small in general. Our universe is less than 1018 seconds old but in cryptology one works
with groups of the large orders like 10400. ] In dynamical systems theory one has tricks
however to estimate at least. One can for example look at a large time t for which the evolution
is close to the identity (the motion of the planets is pretty close to a quasi periodic motion and the
waiting time is reasonably computable once one knows the frequencies). This means that one can
approximate the motion by linear motion on a torus.
In the linear case, the discrete log problem is solvable.
My own work in crypto has motivated my own work on
the multivariable Chinese remainder theorem . And
here are some slides from
a math circle from April 15, 2014 showing the connection. (See especially from page 26 on on
these slides] So, as a dynamical systems person, one would try to attack the discrete log problem in trying
to see whether the dynamical system exp: x goes to a*x in the group features some patterns. It is not
excluded that by investigating small orbits one could get information about the large scale motion
similarly as we do with the 3 body problem.
See the Three body problem 2024 part IThree body problem 2024 part II
in the math in movies collection.
