home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #18 / NN_1992_18.iso / spool / sci / crypt / 2987 < prev    next >
Encoding:
Internet Message Format  |  1992-08-21  |  1.6 KB
  1. Path: sparky!uunet!cis.ohio-state.edu!ucbvax!virtualnews.nyu.edu!brnstnd
  2. From: brnstnd@nyu.edu (D. J. Bernstein)
  3. Newsgroups: sci.crypt
  4. Subject: Re: RSA-129 contest
  5. Message-ID: <5976.Aug2123.46.0692@virtualnews.nyu.edu>
  6. Date: 21 Aug 92 23:46:06 GMT
  7. References: <9208202353.AA21728@ucbvax.Berkeley.EDU>
  8. Organization: IR
  9. Lines: 29
  10.  
  11. In article <9208202353.AA21728@ucbvax.Berkeley.EDU> jbs@WATSON.IBM.COM writes:
  12.   [ Bob Silverman writes: ]
  13. > > I estimate that to be competitive with the Quadratic sieve they need
  14. > > to find coefficients of 'about' 14 digits.  I am not sure it is
  15. > > possible.
  16. > Well, let us estimate how many numbers between 10**128 and
  17. > 10**129 can be so represented.
  18.  
  19. Keep in mind that---even if Bob's pessimistic estimate of 14 digits is
  20. close to reality, which I very much doubt---f(m) can be any multiple of
  21. n, and two-variable polynomials f(m_1,m_2) also work for GNFS. If we
  22. were to allow 10^5 multiples of n, 10^24 choices of m_1, 10^24 choices
  23. of m_2, and 10^14 choices of each c_i, then there would be roughly 10^9
  24. sufficiently small polynomials for RSA-129. So from a theoretical point
  25. of view there's no problem.
  26.  
  27. In practice, of course, finding a good polynomial takes a lot of work,
  28. which is why we're running this contest. Obviously it doesn't make sense
  29. to spend more time searching for good polynomials than it would take to
  30. actually run GNFS, but the latter will take months or years on high-end
  31. hardware; we certainly haven't reached the break-even point.
  32.  
  33. Anyone who missed the original contest announcement two weeks ago can
  34. send mail to factor@src.dec.com with the two lines
  35.  
  36.   path#yourname@your.host
  37.   rsastatus#
  38.  
  39. ---Dan
  40.