home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1993 #3 / NN_1993_3.iso / spool / sci / crypt / 7077 < prev    next >
Encoding:
Internet Message Format  |  1993-01-21  |  1.5 KB
  1. Xref: sparky sci.crypt:7077 sci.math:18621
  2. Newsgroups: sci.crypt,sci.math
  3. Path: sparky!uunet!gatech!usenet.ins.cwru.edu!agate!linus!linus.mitre.org!gauss!bs
  4. From: bs@gauss.mitre.org (Robert D. Silverman)
  5. Subject: Re: Oh yeah?  Factor this...
  6. Message-ID: <1993Jan22.013643.10520@linus.mitre.org>
  7. Sender: news@linus.mitre.org (News Service)
  8. Nntp-Posting-Host: gauss.mitre.org
  9. Organization: Research Computer Facility, MITRE Corporation, Bedford, MA
  10. References: <1993Jan21.011510.24294@linus.mitre.org> <1993Jan21.205045.13877@netcom.com> <1993Jan22.004018.2036@csi.uottawa.ca>
  11. Distribution: na
  12. Date: Fri, 22 Jan 1993 01:36:43 GMT
  13. Lines: 28
  14.  
  15. In article <1993Jan22.004018.2036@csi.uottawa.ca> cbbrowne@csi.uottawa.ca (Christopher Browne) writes:
  16.  
  17. stuff deleted....
  18.  
  19. :ciphering scheme.  There may be some better methods of searching for
  20. :factor candidates, but there aren't any "silver bullets," or algorithms
  21. :that can factor numbers in time on O(log N) time.  Factoring seems to take
  22. :O(sqrt N) time, which just don't cut it.
  23.  
  24. Not quite. The best rigorously proved upper bound is
  25.  
  26. exp((1+o(1) sqrt(log N log log N))
  27.  
  28. The Number Field Sieve [on some reasonable unproved assumptions] takes
  29.  
  30. exp( (c + o(1))  (log N)^1/3  (log log N)^2/3)
  31.  
  32. with c ~ 1.91
  33.  
  34. These are both sub-exponential and considerably better than O(sqrt(N)).
  35. Even the older Pollard Rho, Squfof and FFT-based P-1 achieved 
  36. O(N^1/4), not O(sqrt(N)).
  37.  
  38. --
  39. Bob Silverman
  40. These are my opinions and not MITRE's.
  41. Mitre Corporation, Bedford, MA 01730
  42. "You can lead a horse's ass to knowledge, but you can't make him think"
  43.