>> A couple of weeks ago, there was discussion about repeating remainders in
>> the LL test. There was general agreement that this would be technically
>> unworkable due to the fact that the remainders are so large. Wouldn't it
>> be possible to store the last 1024 binary digits of the remainder (saving
>> 1024 of these would be only 1MB, not a big deal.)
I make 1024 bits 128 bytes - so you could save 8192 of them in a megabyte...
>> Then we could check for
>> repeating remainders in the last 1024 iterations, without signifigantly
>> restraining performance.
No, because the remainder is modulo 2^p-1, the period could repeat after
more than 1024 iterations if you're just keeping 1024 bits.
Actually I would consider keeping just 64 bits, the chance of getting an
"accidental" match in say 4 million (~2^22) iterations would be only 1 in
2^42 - so, in the rare case that you did get a "hit", you could compute
again & compare the whole residual at the actual iteration counts found,
without too much wasted time or too many false alarms. (Same thing really)
>>If it actually repeated, it could be confirmed in
>> double-checking quite easily.
>
>Once a remainder repeats, does it stay in a loop? If so, you can keep the
>remainder when the iteration number is a power of 2, and detect much longer
>loops.
Must stay in a loop since the test is deterministic - there's no random
element involved (except as a result of a computation error).
(x^2 - 2) mod (2^p - 1) depends on x and p only, and p is fixed.
I don't quite see how this makes it unneccessary to check only iteration
numbers which are powers of 2. How long does it take to find a cycle
length of, say, 127 if you're sampling only powers of 2?
Regards
Brian Beesley
________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
