home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #18 / NN_1992_18.iso / spool / sci / crypt / 2991 < prev    next >
Encoding:
Internet Message Format  |  1992-08-22  |  2.6 KB
  1. Path: sparky!uunet!usc!sdd.hp.com!uakari.primate.wisc.edu!ames!agate!linus!linus.mitre.org!gauss!bs
  2. From: bs@gauss.mitre.org (Robert D. Silverman)
  3. Newsgroups: sci.crypt
  4. Subject: Re: RSA-129 contest
  5. Message-ID: <1992Aug22.113206.4385@linus.mitre.org>
  6. Date: 22 Aug 92 11:32:06 GMT
  7. References: <9208220157.AA02629@ucbvax.Berkeley.EDU> <8146.Aug2205.17.2492@virtualnews.nyu.edu>
  8. Sender: news@linus.mitre.org (News Service)
  9. Organization: Research Computer Facility, MITRE Corporation, Bedford, MA
  10. Lines: 44
  11. Nntp-Posting-Host: gauss.mitre.org
  12.  
  13. In article <8146.Aug2205.17.2492@virtualnews.nyu.edu> brnstnd@nyu.edu (D. J. Bernstein) writes:
  14.  
  15. stuff deleted...
  16.  
  17. >If you feel that way, don't participate. Other people have submitted
  18. >good polynomials and I'm sure the current record won't last long. Nobody
  19. >knows an ``accurate figure of merit'' for GNFS polynomials: nobody has
  20. >ever exhibited an accurate method of estimating how much time GNFS will
  21. >use with various parameters, though GNFS detractors always seem to
  22. >pretend otherwise.
  23.  
  24. Too bad you were not at the public-key crypto conference in Oberwolfach
  25. last year. I presented the results of quite a few benchmarks for the
  26. sieving phase of GNFS on general numbers ranging from 30 to 90 digits.
  27. I would characterize this as an accurate way of estimating how much
  28. time GNFS will take, wouldn't you? I also have at least an order of
  29. magnitude more data than anyone else on the performance of the quadratic
  30. sieve. From this data it is not difficult to project a crossover point
  31. of around 135 digits. The data I have also shows how much speedup is
  32. obtained by reducing the size of the coefficients. My data says that
  33. you will need to find 14 digit coefficients for GNFS to compete with
  34. PPMPQS in doing RSA-129.
  35.  
  36. But Dan says he does not believe this 'pessimistic estimate'.
  37.  
  38. I am not 'pretending' anything, despite Dan's insults. I have real
  39. data.   Dan's labelling of detractors as 'pretending' is both insulting
  40. and unprofessional.
  41.  
  42. Of course he can't back up this belief, because he doesn't have
  43. enough data on the performance of both methods. Of course he is
  44. now obtaining data on the sieving part of GNFS now that he has
  45. it coded. But he still lacks data on QS. Lenstra and Manasse have
  46. done a few dozen numbers with QS. I've done in excess of 500.
  47.  
  48. I am also curious as to whether his comparison with QS also considers
  49. the time to do the final square root along with the sieve time? He
  50. reported that for 2,488+, the final square root took about 15% of the
  51. total sieve time. [1 day vs. 6 days]
  52. --
  53. Bob Silverman
  54. These are my opinions and not MITRE's.
  55. Mitre Corporation, Bedford, MA 01730
  56. "You can lead a horse's ass to knowledge, but you can't make him think"
  57.