Keith W Gerdes wrote:
>
> Before getting bogged down with trying to factor Z, could
> someone please explain what that will gain?? :-)
Well, I admit I'm taking it on faith a little bit myself. Aside from
what Tim Grove said, solving
y = x^2 mod z
for x was described in a book on cryptography that I was looking at, but
the math was a *little* over my head. ;-) But apparently it described a
procedure for doing it if you could factor z. In fact it had a theorem
saying that factoring z was equivalent to solving the equation. But I
probably couldn't carry through the procedure myself, at least not
without spending LOTS of time trying to understand what's going on.
It's like number theory, not regular algebra. I mean they were talking
about things like the Chinese Remainder Theorem, Quadratic Residues,
etc. etc. etc. Basically way over my head... But I was curious if the
number would factor. I figure if it factors, *somebody* will be able to
figure it out. Which is admittedly bass ackwards from what most
sensible people would do. i.e. make sure they can figure it out before
they spend a lot of time factoring ;-) On the other hand, it's not
costing me much to let my old DX4-100 kachug kachug away on it till
power fails. And who knows, maybe someday, somebody will think to try
to factor the number on something really powerful. Maybe somebody knows
somebody who has access to some massively parallel computer already set
up to find prime factors. In some research lab or university
somewhere...
It's like they came up with z quite a long time ago. Maybe it isn't
really the product of two large primes, maybe it's just a big random
number. Maybe it has one or more small factors. If all they had back
then to do their number theory on was an Atari 800 or something maybe a
modern number factorizer on a modern computer can crack it. It's like,
not just computers have evolved, but techniques for factoring numbers
have improved as well. I peeked at the source code for the factorizer
in gp/pari, and it's deep. It's not like it just tries to divide every
prime number less than the square root of the number to be factored into
the number to be factored and look for a zero remainder. It's 124K of
source code, doing things like calculating elliptic curves to find
possible factors. Way over the top... But anyway, I've had it running
for several days now. Still no luck...
Who knows? Maybe it's still too soon. Maybe it would take years of
compute time. I don't know. I can remember trying to factor 2^137-1 a
number of years ago. I let it run on a 10MHz 8086 using Derive for
nearly a month with no result. These days, gp/pari can do it in a few
minutes. I know that 2^137-1 is quite a bit smaller than z, but I have
no idea how to predict how long it should take to do z.
John
--
Archives (includes files) at http://www.biglist.com/lists/stella/archives/
Unsub & more at http://www.biglist.com/lists/stella/
