home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #16 / NN_1992_16.iso / spool / sci / crypt / 2735 < prev    next >
Encoding:
Internet Message Format  |  1992-07-25  |  2.0 KB
  1. Path: sparky!uunet!wupost!zaphod.mps.ohio-state.edu!uakari.primate.wisc.edu!ames!agate!linus!linus.mitre.org!faron!bs
  2. From: bs@faron.mitre.org (Robert D. Silverman)
  3. Newsgroups: sci.crypt
  4. Subject: Re: New record non-networked factorization of difficult number
  5. Message-ID: <1992Jul25.004256.4641@linus.mitre.org>
  6. Date: 25 Jul 92 00:42:56 GMT
  7. References: <26250.Jul2400.28.0492@virtualnews.nyu.edu> <BrwFFH.CAt@cs.psu.edu>
  8. Sender: news@linus.mitre.org (News Service)
  9. Organization: Research Computer Facility, MITRE Corporation, Bedford, MA
  10. Lines: 34
  11. Nntp-Posting-Host: faron.mitre.org
  12.  
  13. In article <BrwFFH.CAt@cs.psu.edu> so@fortran.cs.psu.edu (Nicol C. So) writes:
  14.  
  15. [in reply to a posting by Dan Berstein about the Number Field Sieve]
  16.  
  17.  
  18. >Question: is the technique used here generally applicable to all
  19. >composite numbers or is it applicable to composites of special forms?
  20.  
  21. It is applicable to all numbers,   BUT:
  22.  
  23. The reason they were able to factor a 145 digit number with the method
  24. is because that particular number had a polynomial representation with
  25. VERY small coefficients. The polynomial they used was x^5 + 4, i.e.
  26. single digit coefficients. A general number of 145 digits will yield
  27.  
  28. a polynomial with coefficients around 23-24 digits --> a BIG difference.
  29. The speed of the method strongly depends on the size of these coefficients.
  30.  
  31. My estimates show that the Number Field Sieve becomes faster than the
  32. quadratic sieve for general integers somewhere between 135 and 140 digits.
  33. [Although there are several optimists who think it might be slightly lower].
  34. 135 digits is currently out of reach.
  35.  
  36. Currently, NFS is better than other methods only when one can find
  37. a polynomial representation of the number with very small coefficients.
  38. This restricts the set of numbers that can be factored with the method
  39. to be very small. At present this seems to be an unsurmountable obstacle
  40. to the method. 
  41.  
  42. --
  43. Bob Silverman
  44. These are my opinions and not MITRE's.
  45. Mitre Corporation, Bedford, MA 01730
  46. "You can lead a horse's ass to knowledge, but you can't make him think"
  47.