home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #18 / NN_1992_18.iso / spool / sci / crypt / 2986 < prev    next >
Encoding:
Internet Message Format  |  1992-08-21  |  2.3 KB
  1. Path: sparky!uunet!usc!zaphod.mps.ohio-state.edu!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: <5801.Aug2123.30.1592@virtualnews.nyu.edu>
  6. Date: 21 Aug 92 23:30:15 GMT
  7. References: <9208200145.AA29470@ucbvax.Berkeley.EDU>
  8. Organization: IR
  9. Lines: 37
  10.  
  11. In article <9208200145.AA29470@ucbvax.Berkeley.EDU> jbs@WATSON.IBM.COM writes:
  12. > What is the point of this contest?
  13.  
  14. To find a good polynomial for RSA-129.
  15.  
  16. To factor RSA-129 with GNFS would take many hundreds or thousands of
  17. MIPS-years with a random polynomial. In the two weeks since the contest
  18. was announced, quite a few people have submitted polynomials, and the
  19. best so far---yours---is roughly 1000 times better than random.
  20.  
  21. That means *three times less work* for GNFS. That is a huge difference.
  22.  
  23. Polynomials another 10 or 20 times better could well be good enough for
  24. GNFS to complete in a reasonable time. There are also algebraic criteria
  25. which give some polynomials a significant ``boost.'' For instance, a
  26. polynomial which has many roots modulo 3, 5, and 7 is nearly 100 times
  27. better than a polynomial which has no roots modulo 3, 5, or 7, all else
  28. being equal. (Most polynomials are somewhere in the middle.)
  29.  
  30. Keep in mind that f(m) doesn't have to equal n---it be any positive
  31. multiple. So there are a huge number of polynomials to search through.
  32. Someone who uses clever techniques to search through selected m's may
  33. have a better chance of finding a good polynomial than someone who runs
  34. through billions of m's by brute force (though brute force never
  35. hurts!). It may also be possible to use the extra structure of
  36. two-variable polynomials f(m_1,m_2) to obtain better results there---
  37. certainly the optimal two-variable polynomials have much smaller
  38. coefficients than the optimal one-variable polynomials. These are open
  39. problems. Nobody knows what the best way to search for polynomials is.
  40.  
  41. In any case, the polynomial-searching contest has produced spectacular
  42. results so far. Keep those submissions coming in! I'm sorry I don't yet
  43. have precise estimates of exactly how much RSA-129 GNFS time is saved by
  44. any particular polynomial, but I can assure you that a few weeks of
  45. polynomial searching will be time very, very well spent.
  46.  
  47. ---Dan
  48.