home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #19 / NN_1992_19.iso / spool / sci / crypt / 3003 < prev    next >
Encoding:
Internet Message Format  |  1992-08-25  |  4.2 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: <6049.Aug2520.11.2292@virtualnews.nyu.edu>
  6. Date: 25 Aug 92 20:11:22 GMT
  7. References: <1992Aug22.113206.4385@linus.mitre.org> <21385.Aug2322.57.0292@virtualnews.nyu.edu> <1992Aug24.131342.7986@linus.mitre.org>
  8. Organization: IR
  9. Lines: 88
  10.  
  11. In article <1992Aug24.131342.7986@linus.mitre.org> bs@gauss.mitre.org (Robert D. Silverman) writes:
  12. > :than Adleman's ridiculous estimates a year ago. They are based on
  13. > Ah, yes. Now he's belittling Len Adleman too. A great way to argue.
  14.  
  15. As you know, Bob, Adleman's 330-digit estimates had amazingly little
  16. mathematical validity. This is why you're attacking me rather than
  17. defending Adleman's arguments---there's nothing correct to defend.
  18.  
  19. Adleman stated that it was not clear whether GNFS (without homogeneous
  20. polynomials, of course) would be faster than MPQS for 330-digit numbers.
  21. It was, at that time, quite clear that GNFS would be much faster. It is
  22. easy for an expert to see where Adleman's ``analysis'' departed solid
  23. mathematics and entered the realm of wishful thinking so as to prove his
  24. claim that GNFS was of no practical importance---but the damage has been
  25. done. What was Adleman's motive in trying to discourage practical GNFS
  26. research? What is your motive, Bob?
  27.  
  28. > How do you know they were suboptimal?
  29.  
  30. I know because others at the conference reported that to me.
  31.  
  32. > They might well have been, but since
  33. > you were not at the conference where I presented them,
  34.  
  35. You're frothing, Bob.
  36.  
  37. > Furthermore,
  38. > I asked Arjen how much speedup was obtained by the lattice sieve when you
  39. > did 2,488+, and he said he did not know.
  40.  
  41. Correct. We simply don't have enough data. One might guess any number
  42. between 1.5 and 2.5 for the speedup, but without a non-lattice MasPar
  43. implementation there's no solid basis for comparison. The fact remains
  44. that you didn't take the lattice sieve into account.
  45.  
  46. > :I defy you to make a statement of the form ``GNFS will use more than G
  47. > :MIPS-years to factor RSA-129, while MPQS will take under M MIPS-years to
  48. > :factor RSA-129, and G > M,'' rather than hiding behind loose comparisons
  49. > OK, I will.
  50.   [ ... ]
  51. > I estimate
  52. > that you will need to find 14 digit coefficients to equal this with GNFS.
  53.  
  54. No, Bob, you're still dodging.
  55.  
  56. You have claimed that the crossover point is 135 digits. If the
  57. crossover point is 135 digits then GNFS should be expected to be
  58. somewhat slower than MPQS at 129 digits. Surely you can back up this
  59. statement by presenting your *numerical* estimates for how long GNFS
  60. will take at 129 digits. There is obviously some breakeven point where
  61. searching for a better polynomial won't be worthwhile; surely you can
  62. estimate where that point will be.
  63.  
  64. > Furthermore, as you are well aware (or should be), there is a fair amount
  65. > of variablility in the number of cycles that one obtains from a fixed number
  66. > of relations.
  67.  
  68. Yes, indeed! This is one of the reasons that estimating GNFS yield is so
  69. difficult---and that it's so irresponsible of you to pretend that you do
  70. have accurate estimates.
  71.  
  72. > Rather than state that my claims
  73. > have no validity, why don't you post some estimates of your own, based on
  74. > your experiments, and let others decide who is right.
  75.  
  76. Because, Bob, in case you haven't been listening, my entire point is
  77. that NOBODY HAS ACCURATE ESTIMATES.
  78.  
  79. > You and I both know that between 100 and 150 digits, PPMPQS and GNFS only
  80. > vary in run time by a factor of 2 to 3.
  81.  
  82. No, Bob, I don't know that. That's the estimate which Buhler, Lenstra,
  83. and Pomerance obtained by setting o(1) to 0---but they correctly point
  84. out the inaccuracies involved. You pretend that your numbers are exact.
  85. Why?
  86.  
  87. > :> But he still lacks data on QS. Lenstra and Manasse have
  88. > :> done a few dozen numbers with QS. I've done in excess of 500.
  89. > :I can't speak for either Arjen Lenstra or Mark Manasse, but it seems to
  90. > :me that a few dozen numbers ranging up to 116 digits have far more
  91. > :relevance to 129-digit factorizations than several hundred wimpy
  92. > :numbers.
  93. > Define 'wimpy' please for the rest of the audience.
  94.  
  95. Under 100 digits. You should be ashamed of having impugned the adequacy
  96. of Lenstra and Manasse's data.
  97.  
  98. ---Dan
  99.