home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #16 / NN_1992_16.iso / spool / sci / crypt / 2736 < prev    next >
Encoding:
Internet Message Format  |  1992-07-25  |  2.0 KB
  1. Path: sparky!uunet!cs.utexas.edu!sun-barr!ames!agate!ucbvax!virtualnews.nyu.edu!brnstnd
  2. From: brnstnd@nyu.edu (Dan Bernstein)
  3. Newsgroups: sci.crypt
  4. Subject: Re: New record non-networked factorization of difficult number
  5. Message-ID: <25367.Jul2504.27.2692@virtualnews.nyu.edu>
  6. Date: 25 Jul 92 04:27:26 GMT
  7. References: <26250.Jul2400.28.0492@virtualnews.nyu.edu> <BrwFFH.CAt@cs.psu.edu> <1992Jul25.004256.4641@linus.mitre.org>
  8. Organization: IR
  9. Lines: 37
  10.  
  11. In article <1992Jul25.004256.4641@linus.mitre.org> bs@faron.mitre.org (Robert D. Silverman) writes:
  12. > The reason they were able to factor a 145 digit number
  13.  
  14. (2^488 + 1)/257 had 146 digits, last I counted.
  15.  
  16. > A general number of 145 digits will yield
  17. > a polynomial with coefficients around 23-24 digits --> a BIG difference.
  18.  
  19. Take any 150-digit number n. Now try to find positive integers m and m',
  20. together with six coefficients c_0 through c_5, such that n = c_0 m'^5 +
  21. c_1 m'^4 m + ... + c_5 m^5. We could of course choose m around 25
  22. digits, and m' = 1, and write n in base m, giving coefficients around 25
  23. digits. This is where Bob gets his estimates.
  24.  
  25. If you choose all eight of these parameters up to 25 digits then you get
  26. about 200 digits to play with---and n has only 150 digits. So we should
  27. in theory (modulo some plausible heuristics) be able to chop those extra
  28. 50 digits out of the c's, ending up with 25 - 50/6 < 17 digits per c for
  29. some pair (m,m').
  30.  
  31. Exercise for the reader (yes, kids, you can try this at home!): Can you
  32. compute m and m' for RSA-150 so that the c_i are smaller than ``23-24
  33. digits''? Can you beat Bob's best polynomial? Hint: Brute force.
  34.  
  35. Now can you compute m and m' so that the c_i are under 20 digits?
  36.  
  37. > The speed of the method strongly depends on the size of these coefficients.
  38.  
  39. This is true.
  40.  
  41. > My estimates show that the Number Field Sieve becomes faster than the
  42. > quadratic sieve for general integers somewhere between 135 and 140 digits.
  43.  
  44. Ah, yes, and didn't Adleman's estimates a year ago ``show'' that GNFS
  45. would probably be slower than MPQS around 330 digits?
  46.  
  47. ---Dan
  48.