Re: A89: Linux Port for 89/92
[Prev][Next][Index][Thread]
Re: A89: Linux Port for 89/92
Why does n have a lower limit of 2^504??
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...
(and if it does, in fact, have a lower limit of 2^504, that makes it
easier!)
A factoring prrogram 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? 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.
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...
-Miles Raymond EML: m_rayman@bigfoot.com
ICQ: 13217756 IRC: Killer2 AIM: KilIer2 (kilier2)
http://www.bigfoot.com/~m_rayman/
----- Original Message -----
From: Johan <johei804@student.liu.se>
To: <assembly-89@lists.ticalc.org>
Sent: Thursday, July 15, 1999 12:27 PM
Subject: Re: A89: Linux Port for 89/92
> On Thu, Jul 15, 1999 at 12:05:16 -0500, Miles Raymond wrote:
> >
> > Does this mean that we are dealing with a number that could be as large
as
> >
13,407,807,929,942,597,099,574,024,998,205,846,127,479,365,820,592,393,377,7
> >
23,561,443,721,764,030,073,546,976,801,874,298,166,903,427,690,031,858,186,4
> > 86,050,853,753,882,811,946,569,946,433,649,006,084,096
> > ?? (actually, a little less than that, because that # doesn't have only
2
> > factors... hehe, it has 512 of them!! =)
>
> Yes, the number can be that large. :(
> It is actually 2^504 < n < 2^512.
>
> > What I suggest is that someone with a really fast computer make a
program to
> > start at 2^512-1 and find the factors of that #, and if there are only
2, to
> > put them in a list, then decrease the # by 2 and do it again. I'm not
> > saying that it'll give the answer right away, since there are trillions
and
> > trillions of digits in each number, but then we will have a list of all
of
> > the _possible_ values of n, p, and q.
>
> Can you imagine how long that list would be?
> We only need to find the factors of *one* number, n, but that still takes
a
> *very* long time, even for a *really* fast computer. (Have you read the
> questions/answers in the FAQ about factoring?)
>
> file://Johan
Follow-Ups:
References: