home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1993 #3 / NN_1993_3.iso / spool / sci / crypt / 7076 < prev    next >
Encoding:
Internet Message Format  |  1993-01-21  |  2.0 KB
  1. Xref: sparky sci.crypt:7076 sci.math:18620
  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.005608.9812@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: <1993Jan20.232616.5748@zip.eecs.umich.edu> <1993Jan21.011510.24294@linus.mitre.org> <1993Jan21.205045.13877@netcom.com>
  11. Distribution: na
  12. Date: Fri, 22 Jan 1993 00:56:08 GMT
  13. Lines: 28
  14.  
  15. In article <1993Jan21.205045.13877@netcom.com> strnlght@netcom.com (David Sternlight) writes:
  16. :In article <1993Jan21.011510.24294@linus.mitre.org> bs@gauss.mitre.org (Robert D. Silverman) writes:
  17. :>27392450308603031423410234291674686281194364367580914627947367941608692026226993634332118404582438634929548737283992369758487974306317730580753883429460344956410077034761330476016739454649828385541500213920807
  18. :>:
  19. :>:Can you factor this number [in your lifetime]?  If so, you may be
  20. :> 
  21. :>What is the source for this number? Is it a random integer? Is it
  22. :>an RSA number, constructed as the product of nearly equal primes?
  23. :>If the latter it is out of current computational range.
  24. :
  25. :(Correcting a previous post)
  26. :Couldn't you take the approximate square root of the number, truncate the
  27. :result, and then start searching up and down from there if the number is the
  28. :product of two nearly equal primes?
  29.  
  30. The above number is 209 digits. Its square root is 105 digits. Let's
  31. say it is the product of primes, the first 10 digits of which are the
  32. same. Thus, they are nearly equal. That only leaves about 10^95 numbers
  33. to search by the proposal you make.
  34.  
  35. The method you suggest is known as Fermat's method. It is still
  36. only 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.