home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #19 / NN_1992_19.iso / spool / sci / crypt / 2993 < prev    next >
Encoding:
Internet Message Format  |  1992-08-23  |  2.3 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: <21385.Aug2322.57.0292@virtualnews.nyu.edu>
  6. Date: 23 Aug 92 22:57:02 GMT
  7. References: <9208220157.AA02629@ucbvax.Berkeley.EDU> <8146.Aug2205.17.2492@virtualnews.nyu.edu> <1992Aug22.113206.4385@linus.mitre.org>
  8. Organization: IR
  9. Lines: 41
  10.  
  11. In article <1992Aug22.113206.4385@linus.mitre.org> bs@gauss.mitre.org (Robert D. Silverman) writes:
  12. > I presented the results of quite a few benchmarks for the
  13. > sieving phase of GNFS on general numbers ranging from 30 to 90 digits.
  14.  
  15. And you try to extrapolate by 45 digits from your highly suboptimal
  16. polynomial choices. You didn't even take Pollard's lattice sieve into
  17. account.
  18.  
  19. I defy you to make a statement of the form ``GNFS will use more than G
  20. MIPS-years to factor RSA-129, while MPQS will take under M MIPS-years to
  21. factor RSA-129, and G > M,'' rather than hiding behind loose comparisons
  22. such as ``I estimate the crossover point to be around 135 digits.''
  23. Either make a definite statement so that I can demonstrate by actual
  24. experiments that you're wrong, or admit that you can't accurately
  25. estimate the time taken by GNFS.
  26.  
  27. > Dan's labelling of detractors as 'pretending' is both insulting
  28. > and unprofessional.
  29.  
  30. I don't think so. Your estimates of GNFS's speed have no more validity
  31. than Adleman's ridiculous estimates a year ago. They are based on
  32. wishful thinking (such as your incorrect estimate of coefficient digits
  33. for a 145-digit number on sci.crypt a few weeks ago) as well as neglect
  34. of existing algorithmic improvements (such as the special-q method).
  35.  
  36. It was irresponsible of Adleman to state that it wasn't clear whether
  37. GNFS would be faster than MPQS for 330-digit numbers. It is just as
  38. irresponsible of you to claim a 135-digit crossover point. It is neither
  39. insulting nor unprofessional for me to demand that you make your
  40. estimates of GNFS speed sufficiently detailed that I can prove them
  41. false.
  42.  
  43. > But he still lacks data on QS. Lenstra and Manasse have
  44. > done a few dozen numbers with QS. I've done in excess of 500.
  45.  
  46. I can't speak for either Arjen Lenstra or Mark Manasse, but it seems to
  47. me that a few dozen numbers ranging up to 116 digits have far more
  48. relevance to 129-digit factorizations than several hundred wimpy
  49. numbers.
  50.  
  51. ---Dan
  52.