🚀 go-pugleaf

In article <1993Jan21.205045.13877@netcom.com> strnlght@netcom.com (David Sternlight) writes:
>In article <1993Jan21.011510.24294@linus.mitre.org> bs@gauss.mitre.org (Robert D. Silverman) writes:
>>In article <1993Jan20.232616.5748@zip.eecs.umich.edu> gilgalad@quip.eecs.umich.edu (Ralph Seguin) writes:
>>:
>>27392450308603031423410234291674686281194364367580914627947367941608692026226993634332118404582438634929548737283992369758487974306317730580753883429460344956410077034761330476016739454649828385541500213920807
>>:
>>:Can you factor this number [in your lifetime]?  If so, you may be
>> 
>>What is the source for this number? Is it a random integer? Is it
>>an RSA number, constructed as the product of nearly equal primes?
>>If the latter it is out of current computational range.
>
>(Correcting a previous post)
>Couldn't you take the approximate square root of the number, truncate the
>result, and then start searching up and down from there if the number is the
>product of two nearly equal primes?

Yes, you could.

You'd get a number on the order of 10^100.

You wouldn't need to search UP; only down, because you only really need to
find ONE of the factors.  Once you have one prime factor, the other is
easy to find.

Unfortunately, if you could test 10,000 values per second, it would mean
that the expected time required to factor the number would be of the
order 10^100/(10000) * 1/2 seconds.

That's a LOT of seconds.  On the order of 10^96 seconds.
10^94 minutes
10^92 hours
10^91 days

or in years, on the order of 10^88 years.

Far longer than ANY estimate of the age of the universe.

And if you could speed up the calculations by a factor of 10, it would
still be of the order 10^87 years.  Hardly computable.

And THIS is the reason why RSA is considered to be a comparatively safe
ciphering scheme.  There may be some better methods of searching for
factor candidates, but there aren't any "silver bullets," or algorithms
that can factor numbers in time on O(log N) time.  Factoring seems to take
O(sqrt N) time, which just don't cut it.

-- 
Christopher Browne                |     PGP 2.0 key available
cbbrowne@csi.uottawa.ca           |======================================
University of Ottawa              | Genius may have its limitations, but
Master of System Science Program  | stupidity is not thus handicapped.