home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1993 #3 / NN_1993_3.iso / spool / sci / crypt / 7075 < prev    next >
Encoding:
Internet Message Format  |  1993-01-21  |  2.9 KB
  1. Xref: sparky sci.crypt:7075 sci.math:18615
  2. Newsgroups: sci.crypt,sci.math
  3. Path: sparky!uunet!cs.utexas.edu!torn!nott!uotcsi2!news
  4. From: cbbrowne@csi.uottawa.ca (Christopher Browne)
  5. Subject: Re: Oh yeah?  Factor this...
  6. Message-ID: <1993Jan22.004018.2036@csi.uottawa.ca>
  7. Sender: news@csi.uottawa.ca
  8. Nntp-Posting-Host: prgf
  9. Organization: Dept. of Computer Science, University of Ottawa
  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 93 00:40:18 GMT
  13. Lines: 52
  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. >>In article <1993Jan20.232616.5748@zip.eecs.umich.edu> gilgalad@quip.eecs.umich.edu (Ralph Seguin) writes:
  18. >>:
  19. >>27392450308603031423410234291674686281194364367580914627947367941608692026226993634332118404582438634929548737283992369758487974306317730580753883429460344956410077034761330476016739454649828385541500213920807
  20. >>:
  21. >>:Can you factor this number [in your lifetime]?  If so, you may be
  22. >> 
  23. >>What is the source for this number? Is it a random integer? Is it
  24. >>an RSA number, constructed as the product of nearly equal primes?
  25. >>If the latter it is out of current computational range.
  26. >
  27. >(Correcting a previous post)
  28. >Couldn't you take the approximate square root of the number, truncate the
  29. >result, and then start searching up and down from there if the number is the
  30. >product of two nearly equal primes?
  31.  
  32. Yes, you could.
  33.  
  34. You'd get a number on the order of 10^100.
  35.  
  36. You wouldn't need to search UP; only down, because you only really need to
  37. find ONE of the factors.  Once you have one prime factor, the other is
  38. easy to find.
  39.  
  40. Unfortunately, if you could test 10,000 values per second, it would mean
  41. that the expected time required to factor the number would be of the
  42. order 10^100/(10000) * 1/2 seconds.
  43.  
  44. That's a LOT of seconds.  On the order of 10^96 seconds.
  45. 10^94 minutes
  46. 10^92 hours
  47. 10^91 days
  48.  
  49. or in years, on the order of 10^88 years.
  50.  
  51. Far longer than ANY estimate of the age of the universe.
  52.  
  53. And if you could speed up the calculations by a factor of 10, it would
  54. still be of the order 10^87 years.  Hardly computable.
  55.  
  56. And THIS is the reason why RSA is considered to be a comparatively safe
  57. ciphering scheme.  There may be some better methods of searching for
  58. factor candidates, but there aren't any "silver bullets," or algorithms
  59. that can factor numbers in time on O(log N) time.  Factoring seems to take
  60. O(sqrt N) time, which just don't cut it.
  61.  
  62. -- 
  63. Christopher Browne                |     PGP 2.0 key available
  64. cbbrowne@csi.uottawa.ca           |======================================
  65. University of Ottawa              | Genius may have its limitations, but
  66. Master of System Science Program  | stupidity is not thus handicapped.
  67.