home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #19 / NN_1992_19.iso / spool / sci / crypt / 3064 < prev    next >
Encoding:
Internet Message Format  |  1992-08-31  |  2.8 KB
  1. Path: sparky!uunet!gatech!darwin.sura.net!zaphod.mps.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: <18112.Aug3004.30.1292@virtualnews.nyu.edu>
  6. Date: 30 Aug 92 04:30:12 GMT
  7. References: <1992Aug26.132003.5928@linus.mitre.org> <19122.Aug2700.12.0192@virtualnews.nyu.edu> <1992Aug27.111639.16325@linus.mitre.org>
  8. Organization: IR
  9. Lines: 47
  10.  
  11. In article <1992Aug27.111639.16325@linus.mitre.org> bs@gauss.mitre.org (Robert D. Silverman) writes:
  12. > :Why are you trying to discourage people from
  13. > :entering the RSA-129 contest, Bob?
  14. > Now this last accusation really is obnoxious, because it puts words
  15. > in my mouth that I have never said.
  16.  
  17. Bob, you stated that a 6-7 digit improvement in GNFS polynomials in this
  18. range would result in only a 2x speedup. If this were true, it would put
  19. a rather small cap on the possible benefits of the RSA-129 contest.
  20.  
  21. It is not, in fact, true. It is wildly inaccurate: as I pointed out
  22. before, such an improvement could easily gain an order of magnitude in
  23. speed. (For instance, p(9) is more than ten times p(10), p being the rho
  24. function; here N(a,b) is compared to (max AFB)^9.) You had your chance
  25. to retract the statement, Bob, and you failed.
  26.  
  27. Someone who believed your misstatement about speedups would obviously be
  28. discouraged from entering the RSA-129 contest. Bob, what's your
  29. motivation? Why are you trying to squash interest in GNFS? You're
  30. achieving the effect of lying to the public, even if you don't mean to
  31. do so. I don't care whether it's obnoxious of me to point this out---I
  32. can't sit by and watch you corrupt the views of people who haven't
  33. learned about GNFS and can only go by what they hear from others.
  34.  
  35. > All you are doing is gainsaying my data without posting data of your own.
  36.  
  37. That's right. The bulk of data which I have is part of an article I'm
  38. writing with Arjen Lenstra on our GNFS implementation. That data, like
  39. your data, is not sufficient to conclude that GNFS will probably be
  40. slower than MPQS at 129 digits. Yet you keep stating this conclusion.
  41.  
  42. > you are confusing the two functions.
  43.  
  44. My apologies. I mistakenly thought that you were talking about Dickman's
  45. rho function, which (I can say with some assurance now that I've checked
  46. my references) a few people attribute to Knuth and Trabb Pardo (because
  47. Knuth and Trabb Pardo did publish some things about it).
  48.  
  49. I guess you are referring to the logarithmic sum that Schroeppel
  50. originally suggested for choosing multiples for the continued fraction
  51. method. If so, I am astounded at your statement that it would be nice to
  52. have such a function for the algebraic side of GNFS---everyone knows
  53. what it is, namely the sum of log p times the (easily computable)
  54. probability that a coprime pair a,b has N(a,b) divisible by p^d, over
  55. all p and d.
  56.  
  57. ---Dan
  58.