home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #18 / NN_1992_18.iso / spool / sci / crypt / 2989 < prev    next >
Encoding:
Internet Message Format  |  1992-08-21  |  2.7 KB
  1. Path: sparky!uunet!cis.ohio-state.edu!pacific.mps.ohio-state.edu!linac!att!ucbvax!WATSON.IBM.COM!jbs
  2. From: jbs@WATSON.IBM.COM
  3. Newsgroups: sci.crypt
  4. Subject: RSA-129 contest
  5. Message-ID: <9208220157.AA02629@ucbvax.Berkeley.EDU>
  6. Date: 22 Aug 92 01:13:04 GMT
  7. Sender: daemon@ucbvax.BERKELEY.EDU
  8. Lines: 41
  9.  
  10.  
  11.          Dan Berstein posts:
  12. :To factor RSA-129 with GNFS would take many hundreds or thousands of
  13. :MIPS-years with a random polynomial. In the two weeks since the contest
  14. :was announced, quite a few people have submitted polynomials, and the
  15. :best so far---yours---is roughly 1000 times better than random.
  16. :being equal. (Most polynomials are somewhere in the middle.)
  17.          Actually it is about 100 times better than random using
  18. your stated figure of merit.  More to the point it is only about 10
  19. times better than simply trying a few million values of m.
  20.          Dan Berstein also posts:
  21. :Keep in mind that f(m) doesn't have to equal n---it be any positive
  22. :multiple. So there are a huge number of polynomials to search through.
  23.          Since the density of good representations for k*n goes as
  24. k**(-9/4) considering multiples of n is unlikely to give a significant
  25. improvement.
  26.          Dan Berstein also posts:
  27. :In any case, the polynomial-searching contest has produced spectacular
  28. :results so far. Keep those submissions coming in! I'm sorry I don't yet
  29. :have precise estimates of exactly how much RSA-129 GNFS time is saved by
  30. :any particular polynomial, but I can assure you that a few weeks of
  31. :polynomial searching will be time very, very well spent.
  32.          I must disagree, extensive searches without an accurate figure
  33. of merit are basically a waste of time.  I have little enthusiasm for
  34. burning weeks of computer time searching for good fifth degree poly-
  35. nomials only to learn that a more complete figure of merit shows that
  36. I should have been searching for sixth degree polynomials.
  37.          Dan Berstein also posts:
  38. :Keep in mind that---even if Bob's pessimistic estimate of 14 digits is
  39. :close to reality, which I very much doubt---f(m) can be any multiple of
  40. :n, and two-variable polynomials f(m_1,m_2) also work for GNFS. If we
  41. :were to allow 10^5 multiples of n, 10^24 choices of m_1, 10^24 choices
  42. :of m_2, and 10^14 choices of each c_i, then there would be roughly 10^9
  43. :sufficiently small polynomials for RSA-129. So from a theoretical point
  44. :of view there's no problem.
  45.          As I point out above, considering all multiples of n increases
  46. the density of representations (of the form f(m), f degree 5) by, sum
  47. over k of k**(-9/4), which is less than 2 (not 10**5).  I can't comment
  48. on searching for two-variable polynomials without knowing the figure
  49. of merit.
  50.                        James B. Shearer
  51.