home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #18 / NN_1992_18.iso / spool / sci / crypt / 2990 < prev    next >
Encoding:
Internet Message Format  |  1992-08-21  |  2.5 KB
  1. Path: sparky!uunet!cis.ohio-state.edu!pacific.mps.ohio-state.edu!linac!att!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: <8146.Aug2205.17.2492@virtualnews.nyu.edu>
  6. Date: 22 Aug 92 05:17:24 GMT
  7. References: <9208220157.AA02629@ucbvax.Berkeley.EDU>
  8. Organization: IR
  9. Lines: 48
  10.  
  11. In article <9208220157.AA02629@ucbvax.Berkeley.EDU> jbs@WATSON.IBM.COM writes:
  12. > More to the point it is only about 10
  13. > times better than simply trying a few million values of m.
  14.  
  15. 10 times better means about 40% reduction in run time.
  16.  
  17. We are talking about *years* on a supercomputer---and don't think that
  18. RSA-129 is the only number that anyone wants to factor! I often spend
  19. time optimizing a section of code responsible for less than one percent
  20. of the run time of a program---and then another section, another
  21. section, another section, and all of a sudden I try the program and it's
  22. five or ten percent faster than before. This is a good thing.
  23.  
  24. James, if you don't appreciate the value of a 40% speedup, don't
  25. participate in the contest.
  26.  
  27. > Since the density of good representations for k*n goes as
  28. > k**(-9/4) considering multiples of n is unlikely to give a significant
  29. > improvement.
  30.  
  31. I don't know what grounds you're arguing from. Nor do I particularly
  32. care. You were worrying about running out of good polynomials. The fact
  33. is that multiples of n give polynomials nearly as good as polynomials
  34. for n itself.
  35.  
  36. > I must disagree, extensive searches without an accurate figure
  37. > of merit are basically a waste of time.
  38.  
  39. If you feel that way, don't participate. Other people have submitted
  40. good polynomials and I'm sure the current record won't last long. Nobody
  41. knows an ``accurate figure of merit'' for GNFS polynomials: nobody has
  42. ever exhibited an accurate method of estimating how much time GNFS will
  43. use with various parameters, though GNFS detractors always seem to
  44. pretend otherwise.
  45.  
  46. The point of this contest is not to find the minimum value of the
  47. total-coefficients-times-m measure, although that measure isn't bad; the
  48. reason that I specified an upper limit for that measure was to weed out
  49. contest entrants who weren't serious. The point of this contest (at
  50. least as I see it---I can't speak for Arjen Lenstra) is to find a
  51. reasonable number of reasonably good polynomials in the hope of
  52. minimizing the time needed for GNFS to factor RSA-129.
  53.  
  54. >          Dan Berstein also posts:
  55.  
  56. Bernstein. Sure you didn't drop any digits in those polynomials? :-)
  57.  
  58. ---Dan
  59.