more on Possible Crypto Breakthrough?

[Dave Farber <dave () farber net>]

------ Forwarded Message
From: Seth Finkelstein <sethf () sethf com>
Date: Sun, 06 Apr 2003 06:33:49 -0400
To: Dave Farber <dave () farber net>
Subject: Re: [IP] Possible Crypto Breakthrough?

[For IP]
    Dave, that article is, unsurprisingly, sensationalized. See:

"The PRIMES is in P little FAQ"
http://crypto.cs.mcgill.ca/~stiglic/PRIMES_P_FAQ.html

Q12. Could this result break cryptographic algorithms?

No. As mentioned above, fast randomized algorithms for primality
testing were already known, and in fact they are necessary just to
make most known public key cryptosystems feasible!

Some people confuse the factorization problem with the problem of
distinguishing prime numbers from composite numbers.  The
factorization problem is: given an integer n, try to find the prime
numbers which when multiplied together give n.  The fundamental
theorem of arithmetic states that every integer n can indeed be
factored into prime numbers, and in a unique way, so the problem makes
sense for any integer.  If one could efficiently factor large
integers, then certain cryptographic algorithms would be broken (such
as the famous RSA encryption and signature schemes).  The fact that
PRIME has been found to be in P cannot be used to break any
cryptographic algorithms.

Q13. Does this result have any impact in cryptography at all?

Not in any obvious ways. Certain algorithms need to generate prime
numbers in order to construct cryptographic keys, but algorithms to
accomplish this which can be executed very efficiently already existed
before the result in [1].  The most commonly used ones have a
probability of error, but this error can be made to be arbitrarily
small (see question 9) and thus they give us practically the same
assurance as the algorithm proposed in P.  These algorithms that are
commonly used in practice are actually faster than the ones proposed
in [1].  The result in [1] is a very important one in complexity
theory, but probably have no (practical) impact in cryptography.

* [1]  Manindra Agrawal, Neeraj Kayal and Nitin Saxena, PRIMES is in P:

      http://www.cse.iitk.ac.in/news/primality.html

Also http://www.sciencenews.org/20021026/bob9.asp

-- 
Seth Finkelstein  Consulting Programmer  sethf () sethf com  http://sethf.com
Anticensorware Investigations - http://sethf.com/anticensorware/
Seth Finkelstein's Infothought blog - http://sethf.com/infothought/blog/


------ End of Forwarded Message

-------------------------------------
You are subscribed as interesting-people () lists elistx com
To manage your subscription, go to
  http://v2.listbox.com/member/?listname=ip

Archives at: http://www.interesting-people.org/archives/interesting-people/