On 15 Jun 99, at 14:40, [EMAIL PROTECTED] wrote:
> I thought we had discussed "S recycling" before and came to the conclusions:
> A: Detecting whether S repeats or not is infeasible, especially if the
> cycling period is even moderately long. You have to spend CPU time to do it,
> and keep lots of storage space handy.
Actually this is NOT true, if we're talking about tracking iterations
up to 2^n then I can find the cycle with a storage space of 8n bytes,
provided you let me have a "false alarm" rate of 1 in 2^64. If you
were to build this in, then the extra CPU time would be minimal.
However:
> B: Cycling before the P-1th iteration is unlikely in its own right.
I thought we had more or less worked out (not formally proved - but a
solid argument) that if P is prime, cycling _won't_ occur in the
first P-2 iterations. Pity, because the existence of a cycle in the
first P-2 iterations _proves_ 2^P-1 composite without having to run
all the iterations (if it starts cycling, it _can't_ get to 0 at
iteration P-2)
Regards
Brian Beesley
________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
