Re: A89: Linux Port for 89/92
[Prev][Next][Index][Thread]
Re: A89: Linux Port for 89/92
On Thu, Jul 15, 1999 at 14:46:41 -0500, Miles Raymond wrote:
>
> Why does n have a lower limit of 2^504??
The numbers are always 64 bytes long, and the lowest number that needs 64
bytes is 2^504, the largest number is 2^512-1.
n (on the TI89) is ...
7,199,583,456,868,477,363,672,043,865,116,047,229,712,788,448,020,653,
515,684,330,784,137,805,088,971,433,273,011,970,552,138,960,583,799,
368,215,373,582,308,591,928,985,045,059,261,105,298,431,035,818,727.
(I'm not 100% sure, because I haven't studied the number format in detail
yet, and I might have made a typo somewhere. So don't waste your time on
factoring this number, ok? :) It's presented here so you can get a feeling
of the problem we're facing...)
> Yes, I know how long it can take to factor, since I tried factor(2^512-1) on
> my TI-89 with no result for about an hour... But I think there can be a
> quicker way to get the results we want, not neccessarily to factor it...
According to my TI89 Guide Book, factoring a 100-digit number can take more
than a century on the calc... nice try ;)
> (and if it does, in fact, have a lower limit of 2^504, that makes it
> easier!)
The numbers less than 2^504 is 0.4% of all numbers less than 2^512... it's
not a "big" win...
> A factoring program works something like divide by 2 till not possible
> (with integer result), then 3 till not possible, then 5, then the next
> prime, and so on... right?
No, that's the slowest way to factor a number. There are many faster
algorithms. (See the RSA Labs FAQ.)
> But because these are special circumstances, we
> don't have to check for 2 (because we skip all of the evens) and if our
> number _is_ divisible by a low prime, then we can skip it, assuming that
> niether p nor q is a small prime. Where you draw the line is your choice.
I don't *know* anything about p and q, except that their product is n, but I
assume that they're somewhere between 2^128..2^384.
> Or, if you don't like that, (I thought of another way while typing that) you
> can skip the number when you find 3 factors, or have a little of both. This
> will decrease the time necessary to find out list of possible n's...
I still don't think that getting a list of all n's is the way to go... this
list would be H-U-G-E.
The problem is that we want the "e" value, and factoring n to get p and q
seems to be a good place to start, but I'm not a math wiz and someone else
might come up with a better idea... We'll need *lots* of computer power to
break this in reasonable time.
//Johan
Follow-Ups:
References: