home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #19 / NN_1992_19.iso / spool / sci / crypt / 3068 < prev    next >
Encoding:
Text File  |  1992-08-31  |  4.7 KB  |  95 lines
  1. Newsgroups: sci.crypt
  2. Path: sparky!uunet!cis.ohio-state.edu!magnus.acs.ohio-state.edu!usenet.ins.cwru.edu!agate!linus!linus.mitre.org!gauss!bs
  3. From: bs@gauss.mitre.org (Robert D. Silverman)
  4. Subject: Re: RSA-129 contest
  5. Message-ID: <1992Aug31.184355.16783@linus.mitre.org>
  6. Sender: news@linus.mitre.org (News Service)
  7. Nntp-Posting-Host: gauss.mitre.org
  8. Organization: Research Computer Facility, MITRE Corporation, Bedford, MA
  9. References: <19122.Aug2700.12.0192@virtualnews.nyu.edu> <1992Aug27.111639.16325@linus.mitre.org> <18112.Aug3004.30.1292@virtualnews.nyu.edu>
  10. Date: Mon, 31 Aug 1992 18:43:55 GMT
  11. Lines: 82
  12.  
  13. In article <18112.Aug3004.30.1292@virtualnews.nyu.edu> brnstnd@nyu.edu (D. J. Bernstein) writes:
  14. :In article <1992Aug27.111639.16325@linus.mitre.org> bs@gauss.mitre.org (Robert D. Silverman) writes:
  15. :> :Why are you trying to discourage people from
  16. :> :entering the RSA-129 contest, Bob?
  17. :> Now this last accusation really is obnoxious, because it puts words
  18. :> in my mouth that I have never said.
  19. :
  20. :Bob, you stated that a 6-7 digit improvement in GNFS polynomials in this
  21. :range would result in only a 2x speedup. If this were true, it would put
  22. :a rather small cap on the possible benefits of the RSA-129 contest.
  23. :
  24. :It is not, in fact, true. It is wildly inaccurate: as I pointed out
  25. :before, such an improvement could easily gain an order of magnitude in
  26.  
  27. Having done quite a few numbers with the special number field sieve,
  28. I have observed that adding between 25 and 30 decimal digits to the
  29. size of the number I am factoring [using a 5th degree polynomial]
  30. roughly doubles the run time. Adding 30 digits increases the norm
  31. on the integer side by about 6 digits, and does not change the algebraic
  32. side. (that is, as long as the polynomial degree stays the same and the 
  33. coefficients are single digit. [true for the special NFS].)
  34.  If the factor base sizes are well chosen, it therefore seems that
  35. a 6 decimal digit increase on either side of the congruence [but not both]
  36. roughly doubles the run time.
  37.  
  38. :achieving the effect of lying to the public, even if you don't mean to
  39. :do so. I don't care whether it's obnoxious of me to point this out---I
  40. :can't sit by and watch you corrupt the views of people who haven't
  41. :learned about GNFS and can only go by what they hear from others.
  42. :
  43. :> All you are doing is gainsaying my data without posting data of your own.
  44. :
  45. :That's right. The bulk of data which I have is part of an article I'm
  46. :writing with Arjen Lenstra on our GNFS implementation. That data, like
  47. :your data, is not sufficient to conclude that GNFS will probably be
  48. :slower than MPQS at 129 digits. Yet you keep stating this conclusion.
  49. :
  50.  
  51. I'll let others judge your reply for themselves.
  52.  
  53. My data supports a crossover point of 135 digits. It might very well
  54. be conservative by 10 or so digits. However, I have never represented
  55. otherwise than that it is an estimate based upon extrapolations of other data.
  56.  
  57. If you have data that proves me wrong, I would be interested in hearing
  58. about it.
  59.  
  60. However your continued personal attacks upon me because you don't agree
  61. with my estimates are totally uncalled for.
  62.  
  63. :My apologies. I mistakenly thought that you were talking about Dickman's
  64. :rho function, which (I can say with some assurance now that I've checked
  65. :my references) a few people attribute to Knuth and Trabb Pardo (because
  66. :Knuth and Trabb Pardo did publish some things about it).
  67. :
  68. :I guess you are referring to the logarithmic sum that Schroeppel
  69. :originally suggested for choosing multiples for the continued fraction
  70.  
  71. Yes. A variation of this function can also be applied to NFS. As with
  72. QS its value can vary quite a bit for numbers of a fixed size, and it
  73. seems as with QS that the higher the value, the easier it is to factor
  74. a number with NFS. The variation can be substantial.  [I'm sure you know
  75. all this; I'm not trying to be patronizing]
  76.  
  77. :method. If so, I am astounded at your statement that it would be nice to
  78. :have such a function for the algebraic side of GNFS---everyone knows
  79. :what it is, namely the sum of log p times the (easily computable)
  80. :probability that a coprime pair a,b has N(a,b) divisible by p^d, over
  81. :all p and d.
  82.  
  83. Sorry for my lack of precision. I should have said one that can
  84. be computed from the polynomial coefficients directly. Of course if
  85. you know which primes split, which ramify, which are inert, and which
  86. ones split completely, one can compute this. But this means computing
  87. the factor base for every potential polynomial. [which really isn't
  88. that big a deal, I agree, but it is more expensive than changing multipliers
  89. for QS]
  90. --
  91. Bob Silverman
  92. These are my opinions and not MITRE's.
  93. Mitre Corporation, Bedford, MA 01730
  94. "You can lead a horse's ass to knowledge, but you can't make him think"
  95.