Faster way to do LLT?

[1260]

As I understand it, everytime the LLT is done to M(n), computation starts from S(1) mod M(n) up to S(n-1) mod M(n).

Suppose, if the unMODed value of S(n-1) is saved so that it can be used for the next possible candidates and MODed to M(n+k), wouldn't it be faster?

I know that S(n-1) can be extremely large in comparison to M(n), but does using more hard disk space compensate for the time spent in re-computing from S(1)?

[Axel Fox]

Well, I'm not a mathematician, but I think one of the reasons that it must be MODed is this :

The LL Formula always squares the result of the previous iteration (and minus 2, but this is negligable). Considering the current ranges we are testing it is impossible to store such large numbers.

Just start with the S(0) = 4 value and try to square it just 1 million times (and we are currently testing at almost 20 million). You'll see that you'll need WAAAAAAY more space than the largest hard drives or industrial data storage drives on earth. It is therefor impossible to store them.

Axel Fox.

[jocelynl]

In LL test S(n) increases very fast. So it would be useless to store the first few. Imagine 2 squared then 4,16,256,65536, etc... 2^1,2^2,2^4,2^8,2^16,2^32... so it takes no time to reach 2^M-1.
And theses are computed much faster than retreiving it from a disk.


Joss.

[cheesehead]

I know that S(n-1) can be extremely large in comparison to M(n),

It's not always appreciated just how large the unMODed S(i) values get.

The estimated total number of particles (electrons, proton, neutrons, muons, ...) in the known universe is less than 10^100. 10^100 is less than 2^400. If we could use every particle in the universe to store one binary bit, the largest number we could store would be less than 2^(2^400).

Let's look at the unMODed S(i) values:

S(1) = 4 = 2^2

S(2) = (2^2)^2 - 1 = 2^4 - 1 > 2^3

S(3) > (2^3)^2 - 1 > 2^5

S(4) > (2^5)^2 -1 > 2^9

...

For k > 1, S(k) > 2^(2^(k-1)+1)

So S(1000) > 2^(2^999 + 1), which is already way, way above the "universal" storage limit.

And S(1000) isn't very far along the path toward S(several-million).

Edit: I just found an estimate that if the known universe (which is mostly empty space) were packed solid with neutrons (which can be packed more tightly together than other types of particle), it would take 10^128 neutrons. Let's be generous and say it took 10^200 neutrons. 10^200 is less than 2^800. S(1000) still wouldn't fit.

It's not a matter of using more hard disk space. :)

[Axel Fox]

Woooooow, the unMODed LL function raises THAT quickly ???

I don't know what you all think of this post, but I think it's a neat thing to know.

[Prime95]

Originally Posted by Axel Fox

Considering the current ranges we are testing it is impossible to store such large numbers.

Amen. If every proton, neutron, and electron in the universe could store one bit of the S(n) value you wouldn't come close to enough storage space.


Oops, someone beat me to the punch in pointing this out!

[1260]

Okay. If it is really THAT LARGE, isn't there a mathematical conversion to do something similar?

I mean, if S(n-1) = A mod M(n) = B mod M(n+k), then computation can start from S(n-1) to S(n-1+k) for M(n+k) which would be shorter. Is it then possible to solve for B from A, M(n) and M(n+k)?

If not, maybe more values might help:
if S = A mod M(n+a) = B mod M(n+b) = C mod M(n+c) = D mod M(n+d), where a<b<c<d, can D be computed from A, B, and C?

I'm not really familiar with all the theorems in modular arithmetic involving a change of modulo. Is there one related to this problem?

By the way, is the remainder of S(n-1) mod M(n) saved in the results.txt file? Which is it, the Res64 or the WY1?

[cheesehead]

Originally Posted by 1260

Okay. If it is really THAT LARGE, isn't there a mathematical conversion to do something similar?

The world of math will thank you if you can find a shortcut (shorter than L-L, that is), and you can even win a cash prize offered by George/GIMPS. But lots of folks have already tried.

I mean, if S(n-1) = A mod M(n) = B mod M(n+k), then computation can start from S(n-1) to S(n-1+k) for M(n+k) which would be shorter. Is it then possible to solve for B from A, M(n) and M(n+k)?

Yes, but it takes at least as much computation as the straight L-L method, so is not a shortcut.

The catch is that the mod M(n) has been performed on every S(i) value up to S(n-1). That is, there have been a string of up to n-2 divisions by M(n) performed in order to reach the S(n-1) value. If we're going to re-use the S(n-1) value for M(n+K), all of those divisisons would have to be replaced by divisions by M(n+k). Since divisions by M(n+k) produce different remainders than divisions by M(n), this becomes equivalent to re-calculating all the S(i) mod M(n+k) up to S(n-1), then continuing to S(n+k-1). IOW, we'll have to recalculate all the S(i) in mod M(n+k) anyway.

If not, maybe more values might help:
if S = A mod M(n+a) = B mod M(n+b) = C mod M(n+c) = D mod M(n+d), where a<b<c<d, can D be computed from A, B, and C?

Struggle as one might, as far as anyone has yet determined all such attempted shortcuts wind up having to do at least as much computation as the straight L-L method.

By the way, is the remainder of S(n-1) mod M(n) saved in the results.txt file? Which is it, the Res64 or the WY1?

The low-order (right-hand) 64 bits of S(n-1) mod M(n) are saved as the Res64.

[clowns789]

Perhaps you can have something similar to Prime95 that guesses that stuff up.

[only_human]

I believe there is a way to leverage some of the effort of computing a LL sequence for two different numbers under test:

By example I will show the LL sequences for 2^5-1 and 2^7-1 followed by a sequence that attempts to combine some of the work.

Testing 2^5-1, the LL sequence is:
S(0)= 4
S(1)= 4^2 - 2 mod 31 = 14
S(2)=14^2 - 2 mod 31 = 8
S(3)= 8^2 - 2 mod 31 = 0 ; therefore 2^5-1 is prime

Testing 2^7-1, the LL sequence is:
S(0)=4
S(1)= 4^2 - 2 mod 127 =14
S(2)= 14^2 - 2 mod 127 =67
S(3)= 67^2 - 2 mod 127 =42
S(4)= 42^2 - 2 mod 127 =111
S(5)=111^2 - 2 mod 127 =0 ; therefore 2^7-1 is prime

Testing both 2^5-1 and 2^7-1, the LL sequence is:
S(0)=4
S(1)=4^2 - 2 mod (31*127) = 14
S(2)=14^2-2 mod (31*127) = 194
S(3)=194^2-2 mod (31*127) = 2201
at this step,
2201 mod 31=0 therefore 2^5-1 is prime
continue the sequence using
2201 mod 127=42
S(4)=42^2-2 mod 127= 111
S(5)=111^2-2 mod 127=0 ; therefore 2^7-1 is prime

[only_human]

In the message that I posted above, I'd known that since the intermediate values would be computed modulo a value involving maybe twice as many bits, each squared value would be perhaps four times as large as a ordinary LL sequence value.

Another detraction that didn't occur to me so quickly is that the modulo step would no longer be involving a value one less than a power of two. So it might require a true divide rather than anything like convenient method currently used.