Encryption
Relevance to you
Relevance to you even if we do not
connect
My psychology
Primality and IIT Kanpur
RSA
Palladium
ME
My approach
Milestones
Changing the Internet itself
Breaking a major code
I am professionally a computer scientist. Normally, there
is a strict separation of work and family. A lot of what I am doing relates to
family life, languages, biology, and thinking. There are immediate applications
to buying, communicating, disputes, living, education etc. At the end of this
short essay, you will either begin to grasp the enormity of what I am saying
and my honesty in staking out a claim, or think of me as nuts. Either case is
fine by me, in first case I want you to acknowledge the risk you will be taking
in case my dreams do not materialize as a good Hindu wife for whom I am
committed to provide a base but is all risk thereafter. In the latter case, let
me go, for I am likely to be a thorn forever in sides of people who think of me
as an interesting possibility.
Relevance to you even if we do not connect
I am committed to succeed. When I am done, the planet
itself will change with a different approach to intellectual property (all
music, books, software, communication, video, films etc); to buying, selling,
and management; to medicine etc. It will happen within a decade. If only I
could wait – but I can’t stop my biological clock. Now is the time for me.
I
can do many things. But consider marketers, lawyers, and capitalists etc who
seek to dominate me and force me to work for them as sub animals. I will not
yield to them. I have already ensured enormous persistent damage to them on
premature termination of my life for any reason. Basic to what I claim to be
able to do is encryption. There is no magic in what it means – a message is
converted to what looks like gibberish and sent. The receiver can run my
software and convert the gibberish back to what was sent. Provably good
encryption means one can mathematically prove that no interception will allow
the eavesdropper to understand the message, or modify it undetectably,
Relates to music – music source is
encrypted. Same way to film, medical records, books, email, video etc. Relates
to drugs using binary chemicals. Relates to software, which examines a correctly
decoded message prior to doing what they do. Relates to buying and selling for
goods can have buried into them parts that make them useless unless something is
properly decoded.
Primality and IIT Kanpur
I went to IIT Kanpur. My successors made me
proud by solving a 2000-year-old mathematical problem – given a number, is it
prime? A primer number has no factors but 1. The best mathematicians all over
the world tried tussled with it for 2000 years without success. Interesting
enough to get a big splash in New York Times. Practically useless since faster
probabilistic algorithms already exist. Still fascinating theory.
RSA
Stands for the gold standard in public key encryption. Idea is you find
two huge prime numbers, multiply them, and publish just the result. The
published number can be used for encryption. Only some one who knows the
factoring can decode the result. You know it of course. No one else does,
because the problem of factoring huge numbers is quite hard. Except that IIT
Kanpur method will be modified within a year or two to factor huge numbers!
All is not over since there still remain
elliptical functions, and MY method. Nevertheless, a big powerful competitor,
20 years my senior, is about to die. Long live the King!
Palladium
The richest company that strikes fear in heart
of even IBM is Microsoft. Bill Gates who is the richest man alive on earth
heads it. Its products are innovative, useful (windows you use right now) and
also obscenely virus-prone, steal able and unreliable. Not that he does not
recognize the problem. The .net and new Windows Media Player are outcomes
already of the next step – code-named “palladium” inside Microsoft, due out in
2004 or 2005. That will address the insecurities. The only known person who can
derail Microsoft is I. Otherwise they will move from great strength to
overwhelming strength.
ME
I did excellent thesis, got hired at Bell labs without a
track record or knowing anybody on the sheer strength of my accomplishments,
dreams, and total commitment. It was a tumultuous decade for me who moved from
strength to strength without losing sight of objective. I had an accident and
have recovered enough after a decade to be what I was. I need a wonderful
person to love me, mother me, and remake a family for me, in return for total
commitment, guaranteed baseline quality of life, and definite financial and
labor freedom. Not rich, but not poor either, even in the worst case. And
realistic unlimited upside potential.
I impose certain constraints
on myself
Wont be the judge, jury, and
executioner; or turn the other cheek either.
Won’t give up unless I die.
Build family and institutions to survive me in death.
|
You may only be one person to the world,
But you may
also be the world to one person
To love and be loved is to feel the
sun from both sides
|
Milestones
Ability
to speak: (achieved)
Ability
to earn: (getting there) use of encryption
Ability
to write: (getting there) will be able to build documentation, answer emails
Ability
to boilerplate-think (achieved) using unusually high compliance
Ability
to unusual-think (family, wife) must depend on others
>Please read this news item from the New York Times. ...
This primality result has certainly created quite a stir in the math/
computer science/ cryptography community! IITK ka tempo truly high
hai!
The New York Times article said:
> The new algorithm - by Manindra Agrawal, Neeraj Kayal and Nitin
> Saxena of the Indian Institute of Technology in Kanpur -
> guarantees a correct and timely answer.
A key word missing from this is description of "timely" is:
"deterministically". In other words, there are other methods that are
much faster, but are probabilistic in nature, not deterministic, i.e.,
given a number to be tested for primality, they use randomization
methods to return an answer ("Is prime" or "Is not prime") with high
probability of correctness, and this probability can be made as close
to 100% as you like very little additional effort.
The new IITK algorithm is still order N-to-the-12 (possibly
N-to-the-6) where N is the number of digits in the prime number. In
practical cryptography, one uses very large prime numbers that
typically have hundreds of digits, so a method that is even
N-to-the-6th is still too expensive in practice.
For this reason, the probabilistic methods will still be preferable in
practice (that is, until these IITK guys come up with an even faster
deterministic method!)
Nevertheless, it is a truly dramatic fundamental mathematical result.
You probably remember the excitement from a few years ago when Andrew
Wiles, a Princeton mathematician, proved Fermat's Last Theorem (more
accurately a Conjecture, a.k.a. a Statement of Optimism, until he
proved it, when it finally became a Theorem). That result, too, has
no known practical application, but was also a dramatic and exciting
mathematical result (resulting in an absolutely wonderful book and TV
program about the story). However, that proof is long, involved and
requires deep mathematics, inaccessible to mere mortals. In contrast,
the IITK result is extremely short and sweet, adding to the excitement
and admiration.
The New York Times article said:
> Still, for mathematicians and computer scientists, the new
> algorithm represents a great achievement because, they said, it
> simply and elegantly solves a problem that has challenged many of
> the best minds in the field for decades.
What an understatement! They should have said "centuries" or
"millenia", not "decades".
Another interesting IITK side note from this story. Of the three
authors, Agrawal is a professor, and Kayal and Saxena are/were
undergraduate students (I believe this was their B.Tech project!).
And, I have heard that until recenly, they were planning to go to the
U.S. for grad school, but that they have changed their minds and have
decided to enroll at IITK for the Ph.D. program. If this is true,
then this is perhaps a rare phenomenon indeed!
On a more mundane and humorous level, yesterday I was perusing a news
article about this story at:
http://news.com.com/2100-1001-949170.html?tag=fd_top
and came across the following hilarious paragraph:
> Prime efforts may boost encryption
- By Sandeep Junnarkar
Staff Writer, CNET News.com
August 9, 2002, 11:39 AM PT
....
To create encryption keys, RSA uses two huge prime numbers and
multiplies them together to produce an even bigger prime. Testing then
onfirms whether it is in fact a prime number.
It perhaps explains why the writer chose journalism instead of a
technical field that needs any math skills! Somebody must have got
back to him right away, because when I later followed the URL, the
paragraph had been corrected and no longer had this outrageous
statement!
(Reminds me about the joke people used to make about Mamu Chaudhury
teaching electrical engineering:
"There are 3 types of Ohm's law: V=IR, I = V/R and R = V/I, and
given any two, you can derive the third")
Nikhil
** The Wall Street Journal Monday, November 4, 2002
BOOMTOWN By LEE GOMES
A Beautiful Mind From India Is Putting the Internet on Alert
Will Manindra Agrawal bring about the end of the Internet as we know it? The
question is not as ridiculous as it was just two months ago.
Prof. Agrawal is a 36-year old theoretical computer scientist at the Indian
Institute of Technology in Kanpur, India. In August, he solved a problem that
had eluded millennia of mathematicians: developing a method to determine with
complete certainty if a number is prime.
Prime numbers are those divisible only by themselves and
1. While small primes like 5 or 17
are easy to spot, for very large numbers, those hundreds of digits long, there
never had been a formula of "primality testing" that didn't have a
slight chance of error.
Besides being a show-stopping bit of mathematics, the work was big news for the
Internet. Very large prime numbers are the bedrock of Internet encryption, the sort
your browser uses when you are shopping online.
That encryption system takes two big, and secret, prime numbers and multiplies
them. For a bad guy to decrypt your message, he'd need to take the product of that
multiplication and figure out the two prime numbers used to generate it. It's
called the "factoring problem," and fortunately it's something no one
on Earth knows how to do quickly. A speedy method
of factoring would make existing Internet security useless, not a pleasant
thought in this Internet age.
Prof. Agrawal's work involved only testing whether a number is prime, not the
factoring problem. Still, there are enough connections and similarities between
the two that mathematicians and computer scientists from all over the East
Coast flew in to hear Prof. Agrawal on a whirlwind tour last week through the likes
of M.I.T., Harvard and Princeton.
At Princeton, Prof. Agrawal's lecture was the sort of deep math that only the
most beautiful minds could understand. In a subsequent, and more lay-friendly, interview
he said he started his work three years ago. He was dealing with a different
problem, called identity testing, when he noticed the solution hinted at a
potential fresh assault on prime-number testing.
It was a long three years. While no slouch in math, Prof. Agrawal said he
sometimes had to use Google to find information on the more recondite aspects
of number theory. His Eureka! moment came in July. As he was driving his
daughter to school on his motor scooter, a particularly complicated
mathematical set suddenly fell into place.
The computer scientists who heard Prof. Agrawal speak said, with considerable
pride, that he was obviously one of them, because of the way he proceeded
purposely -- "algorithmically" is the word they used – toward his
goal. (As computer scientists tell it, mathematicians tend to be too showy and
discursive about things.)
Prof. Agrawal is the first to admit that his work, for all its elegant math,
has no immediate practical application. He says the current tests for prime numbers,
even with their slight chance of error, are good enough for most people, as
well as extremely fast.
Still, will he now move on to the factoring challenge? Yes, in due time. The
best current method of factoring, he explains, is
the Number Field Sieve. "Best" is a relative term, since all the
computers in the world would still need
untold trillions of years to use the system to factor just one big number.
Prof. Agrawal writes the Number Field Sieve equation on a piece of paper, looks
at it and winces. "Factoring is a natural problem. And natural problems should
have a natural complexity to them. But this,” he says, pointing to the
equation, "this is not natural complexity. This looks very strange. There must
be something more natural than this out there."
What he doesn't yet know, however, is whether a more "natural"
approach to factoring also would be appreciably faster than current methods.
And that, of course, is the $64 billion question.
Most mathematicians say they don't lose any sleep about waking up and finding
the factoring problem solved. It's just too hard, they say. (This difficulty was
the very reason the method was chosen for Internet security in the first
place.)
But others, like Princeton math professor Peter Sarnak who hosted Prof. Agrawal
on campus last week, aren't so convinced of the factoring problem's eternal intractability.
The fact that one venerable mathematics problem has just been solved, said
Prof. Sarnak, might inspire new assaults on factoring, possibly even using some
of Prof. Agrawal's techniques.
Prof. Agrawal said factoring will have to wait a few years; he wants to warm up
with something easier, like "derandomizing polynomial time
algorithms," for instance.
The professor worked on primality testing with two of his graduate students:
Neeraj Kayal and Nitin Saxena. They had planned to join him on his U.S. victory
tour. But the American Embassy in New Delhi, the times being what they are,
refused them visas. The two young geniuses had to stay home.
* Send comments to [email protected], and check back Friday for selected
letters at WSJ.com/BoomTown2.
ABOUT LEE GOMES
Lee Gomes, who writes the Boom Town column on Monday and the Boom Town
Exchange3 on Friday, has been covering various topics, technical and otherwise,
for The Wall Street Journal since 1996. He is a graduate of the University of
Hawaii and the Columbia University Graduate School of Journalism, and lives in San
Francisco.