View Single Post
Old 2003-05-29, 12:28   #8
cheesehead's Avatar
"Richard B. Woods"
Aug 2002
Wisconsin USA

769210 Posts

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.
cheesehead is offline   Reply With Quote