home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #18 / NN_1992_18.iso / spool / sci / crypt / 2974 < prev    next >
Encoding:
Internet Message Format  |  1992-08-20  |  2.9 KB
  1. Path: sparky!uunet!dtix!darwin.sura.net!zaphod.mps.ohio-state.edu!magnus.acs.ohio-state.edu!slc3.ins.cwru.edu!agate!linus!linus.mitre.org!gauss!bs
  2. From: bs@gauss.mitre.org (Robert D. Silverman)
  3. Newsgroups: sci.crypt
  4. Subject: Re: RSA-129 contest
  5. Message-ID: <1992Aug20.134949.4740@linus.mitre.org>
  6. Date: 20 Aug 92 13:49:49 GMT
  7. References: <9208200145.AA29470@ucbvax.Berkeley.EDU>
  8. Sender: news@linus.mitre.org (News Service)
  9. Organization: Research Computer Facility, MITRE Corporation, Bedford, MA
  10. Lines: 54
  11. Nntp-Posting-Host: gauss.mitre.org
  12.  
  13. In article <9208200145.AA29470@ucbvax.Berkeley.EDU> jbs@WATSON.IBM.COM writes:
  14. >
  15. >         D. J. Berstein wrote:
  16. >:To factor RSA-129 with the general number field sieve (GNFS) requires a
  17. >:fifth-degree polynomial
  18. >:
  19. >:  f(x) = c_5 x^5 + c_4 x^4 + c_3 x^3 + c_2 x^2 + c_1 x + c_0,
  20. >:
  21. >:with integer coefficients c_i, and a positive integer m such that f(m)
  22. >:is a small positive integer multiple of RSA-129. Given any random choice
  23. >:of m you can easily expand RSA-129 in base m and find the coefficients
  24. >:c_i. However, for GNFS to finish in a reasonable time, the coefficients
  25. >:must be significantly smaller than random.
  26. >
  27. >         How small do the coefficients have to be?  I have been led to
  28. >believe that the speed of the GNFS overall does not depend much on the
  29. >efficiency of the search for a good polynomial.  If this is the case it
  30. >would seem to be unwise to devote a lot of effort to finding a good poly-
  31. >nomial.  What is the point of this contest?
  32. >                           James B. Shearer
  33.  
  34. This is NOT the case. The performance is VERY sensitive to the size
  35. of the coefficients and it is worthwhile spending a significant amount
  36. of time trying to find small coefficients.
  37.  
  38. For a 5th degree polynomial, 'random' coefficients will be about 21 or 22
  39. digits. One needs to factor two sides of a congruence, one in Z, the other
  40. in Q(alpha). The norms on the integer side will be about 10^32.
  41. [M ~ 10^(130/5) and the average b will be about 10^6]. On the algebraic
  42. side they will be about (10^6)^5 * poly coef or about 10^52.
  43. Of course many will be smaller, [for small b]
  44.  
  45. I estimate that to be competitive with the Quadratic sieve they need
  46. to find coefficients of 'about' 14 digits.  I am not sure it is
  47. possible.
  48.  
  49. Their estimates may, of course, differ depending on their assumptions.
  50.  
  51. I have already done about 1% of the work to factor the RSA-129 with
  52. the two-large-prime variation of the Quadratic Sieve.  I was going
  53. to do it completely, but a deal with Sun to use their internal net
  54. [3000 workstations!] fell through due to management difficulties.
  55. I estimate it was going to take between 5000 and 6000 MIPS-YEARS
  56. to do the computation.
  57.  
  58.  
  59. Now if I could just scrape together 3000 Sparcs for 2-3 months, I
  60. could finish the factorization.
  61.  
  62. --
  63. Bob Silverman
  64. These are my opinions and not MITRE's.
  65. Mitre Corporation, Bedford, MA 01730
  66. "You can lead a horse's ass to knowledge, but you can't make him think"
  67.