home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #19 / NN_1992_19.iso / spool / sci / crypt / 3020 < prev    next >
Encoding:
Internet Message Format  |  1992-08-26  |  2.0 KB
  1. Path: sparky!uunet!cs.utexas.edu!sun-barr!ames!pacbell.com!att!ucbvax!WATSON.IBM.COM!jbs
  2. From: jbs@WATSON.IBM.COM
  3. Newsgroups: sci.crypt
  4. Subject: RSA-129 contest
  5. Message-ID: <9208270030.AA24842@ucbvax.Berkeley.EDU>
  6. Date: 26 Aug 92 23:48:22 GMT
  7. Sender: daemon@ucbvax.BERKELEY.EDU
  8. Lines: 30
  9.  
  10.  
  11.          Robert Silverman posted:
  12. :The problem I have is that one must add the time you spent looking for
  13. :good polynomials to the total run time. However, looking for good
  14. :polynomials is non-deterministic. We do not know of a deterministic
  15. :method which, if you spend time t, you will succeed in reducing the
  16. :coefficients by size F(t). Thus, you cannot predict AT all how long
  17. :a factorization will take. On the other hand, using the base M method,
  18. :while sub-optimal, is deterministic.
  19. :
  20. :If you estimate sieve time is T, and you spend (say) .2T looking
  21. :for a better polynomial, there is no guarantee of finding one, and
  22. :you will have increased total time by 20% for no good reason. Nor do
  23. :you have assurances that spending the extra time will reduce the sieve time
  24. :by more than the time you spent searching.
  25.  
  26.          I don't understand what you are saying here.  Suppose we use a
  27. brute force technique (trying a bunch of different m values) to search
  28. for good polynomials.  We can certainly estimate what measure we will
  29. obtain as a function of the number of m values that we try.  We can then
  30. predict how long the total factorization will take as a function of the
  31. number of trials.  Minimizing this function will tell us how many m
  32. values we should test in order to minimize the expected running time
  33. (this assumes we fix this number in advance, actually we should quit
  34. early if we are lucky, try more if we are unlucky, this is a detail).
  35. It is true this does not give a worst case running time, however is it
  36. not the case that we do not have worst case guaranteed bounds for any
  37. competitive factoring method?  Do you not choose the number of primes
  38. in your factor base by similar reasoning?
  39.                           James B. Shearer
  40.