|
Number
theory hits ‘prime’ time |
||||||
|
|
||||||
|
|
||||||
|
|
||||||
|
||||||
|
|
||||||
|
The New York Times
has reported it, and so have the local Indian newspapers. The internet is abuzz
with news about Mahindra Agrawal, Neeraj Kayal and Nitin Saxena,
mathematicians working in the Indian Institute of Technology, Kanpur, who
have come up with something of a breakthrough in methods to deal with very
large prime numbers. Primes are simply numbers
that do not have divisors. The numbers 3,5,7, for instance, have no divisors
and these are prime numbers. But as the number 9, can be divided by 3, it is
not a prime. We can, of course, easily see that primes just have to be odd
numbers, because even numbers are all divisible by 2! On the face of it this
may seem to be, well, just one feature of a number, which makes things a
little more difficult if it turned up in a fraction, and nothing more. But,
in fact, prime numbers are star players in a fascinating pantomime of
sleights and computing stratagems in ‘pure’ mathematics, which held such
magic for mathematical greats who brought to all scientists the tools with
which to access the secrets of the world over the centuries. This magic comes alive as
soon as we venture beyond the first few hundred primes, which can be easily
identified as primes, by trying a good many divisions. As we reach numbers in
tens of thousands — which are small change for computers — identifying or
producing a prime gets devilishly difficult and generations of mathematicians
have spent lifetimes in devising clever and quicker ways. And now, the age of
computers and e-commerce has discovered a straight commercial worth of doing
just this in the quickest way! A major concern while
buying and selling on the internet is that all sides need to be sure of the
authenticity and credibility of the messages exchanged. One way of making
sure is by agreeing on a secret code every time we transact on the Net. One
trouble with this is that we can hardly arrange, every time, to first meet
the other person and agree on the code. But what is more important is that
even if we did, most codes could be ‘cracked’. And computers have the
persistence and speed to make most codes fairly ‘easy’! A way out was shown by
the devilish difficulty of generating or identifying huge primes. A code is
generated using the result of multiplying a secret, prime number of the
sender with another secret, prime number of the receiver. The code is such
that it could be deciphered by either secret number and by nothing else.
Cracking the code, in fact, consists simply of finding the only two numbers
that go into the product. The security of the
system is that if the two primes chosen are of the order of 2 to the square
of 100 — or ‘2’ multiplied by itself a hundred times — which is a number with
33 digits, the product is too large to be easily broken into its two factors!
The product would typically be around 2 to the square of 200, which is a
number of around 66 digits. Even if only one in a million of all the possible
factors that one could have with 33 digits were checked, to find divisors,
the number of divisions to be done would have 27 digits! If a computer could
do a million divisions a second, the number of seconds it would take would
still have 21 digits. It is not difficult to work out that this would be
thousands and thousands of years! In fact, the methods used are ‘smarter’,
like trying to divide only by primes, but the time taken is still of the same
order. It is in this context
that the study of numbers, and particularly of primes, is of such importance
today. The method the three young mathematicians of IIT, Kanpur, have
developed has been hailed as a solution to one of the great, unsolved
problems in theoretical computer science and computational number theory.
‘‘It’s the best result I’ve heard of in over 10 years,’’ says Shafi
Goldwasser, a professor of computer science at the Massachusetts Institute of
Technology and the Weizmann Institute of Science in Israel. (The writer is a civil
servant working in Mumbai) |
