home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #18 / NN_1992_18.iso / spool / sci / crypt / 2976 < prev    next >
Encoding:
Internet Message Format  |  1992-08-20  |  1.5 KB
  1. Path: sparky!uunet!stanford.edu!agate!ucbvax!WATSON.IBM.COM!jbs
  2. From: jbs@WATSON.IBM.COM
  3. Newsgroups: sci.crypt
  4. Subject: RSA-129 contest
  5. Message-ID: <9208202353.AA21728@ucbvax.Berkeley.EDU>
  6. Date: 20 Aug 92 23:35:49 GMT
  7. Sender: daemon@ucbvax.BERKELEY.EDU
  8. Lines: 23
  9.  
  10.  
  11.           I asked:
  12. :>         How small do the coefficients have to be?  I have been led to
  13. :>believe that the speed of the GNFS overall does not depend much on the
  14. :>efficiency of the search for a good polynomial.  If this is the case it
  15. :>would seem to be unwise to devote a lot of effort to finding a good poly-
  16. :>nomial.  What is the point of this contest?
  17.           Robert D. Silverman replied:
  18. >This is NOT the case. The performance is VERY sensitive to the size
  19. >of the coefficients and it is worthwhile spending a significant amount
  20. >of time trying to find small coefficients.
  21.           and also:
  22. >I estimate that to be competitive with the Quadratic sieve they need
  23. >to find coefficients of 'about' 14 digits.  I am not sure it is
  24. >possible.
  25.           Well, let us estimate how many numbers between 10**128 and
  26. 10**129 can be so represented.  m will be about 10**23 (so that c5*
  27. m**5 is 10**129).  There are about 10**23 choices for m, 10**14 for
  28. each of the ci.  This gives 10**23*(10**14)**6 or 10**107 representa-
  29. tions.  Hence the chance that a random number between 10**128 and
  30. 10**129 has such a representation is below 10**-20.  It would appear
  31. to me that running ECM would be a better bet than this.
  32.                           James B. Shearer
  33.