home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #18 / NN_1992_18.iso / spool / sci / crypt / 2968 < prev    next >
Encoding:
Internet Message Format  |  1992-08-19  |  1.2 KB
  1. Path: sparky!uunet!charon.amdahl.com!pacbell.com!mips!swrinde!cs.utexas.edu!qt.cs.utexas.edu!yale.edu!nigel.msen.com!sdd.hp.com!hplabs!ucbvax!WATSON.IBM.COM!jbs
  2. From: jbs@WATSON.IBM.COM
  3. Newsgroups: sci.crypt
  4. Subject: RSA-129 contest
  5. Message-ID: <9208200145.AA29470@ucbvax.Berkeley.EDU>
  6. Date: 20 Aug 92 01:43:31 GMT
  7. Sender: daemon@ucbvax.BERKELEY.EDU
  8. Lines: 19
  9.  
  10.  
  11.          D. J. Berstein wrote:
  12. :To factor RSA-129 with the general number field sieve (GNFS) requires a
  13. :fifth-degree polynomial
  14. :
  15. :  f(x) = c_5 x^5 + c_4 x^4 + c_3 x^3 + c_2 x^2 + c_1 x + c_0,
  16. :
  17. :with integer coefficients c_i, and a positive integer m such that f(m)
  18. :is a small positive integer multiple of RSA-129. Given any random choice
  19. :of m you can easily expand RSA-129 in base m and find the coefficients
  20. :c_i. However, for GNFS to finish in a reasonable time, the coefficients
  21. :must be significantly smaller than random.
  22.  
  23.          How small do the coefficients have to be?  I have been led to
  24. believe that the speed of the GNFS overall does not depend much on the
  25. efficiency of the search for a good polynomial.  If this is the case it
  26. would seem to be unwise to devote a lot of effort to finding a good poly-
  27. nomial.  What is the point of this contest?
  28.                            James B. Shearer
  29.