About LL test cycles

[JuanTutors]

I assume we know that we can test for LL test cycles pretty easily. Instead of checking for repeated residue, we can store the units digit of the residue after each cycle in ram or on hard drive, and periodically check for repeating digits in this string in less than 1 second, and then verifying a true cycle exists by running a number of steps equal to the cycle length. Is the reason we don't do that that the probability is so low from what we can tell?

[axn]

Originally Posted by dominicanpapi82

Is the reason we don't do that that the probability is so low from what we can tell?

Yep. Totally pointless.

[JuanTutors]

Originally Posted by axn

Yep. Totally pointless.

Thanks! Also, I can hear the bunny's head hit the ground in your avatar. Reminds me of that gif of the utility pole jumping ropes with power lines.

[kriesel]

Originally Posted by dominicanpapi82

I assume we know that we can test for LL test cycles pretty easily. Instead of checking for repeated residue, we can store the units digit of the residue after each cycle in ram or on hard drive, and periodically check for repeating digits in this string in less than 1 second, and then verifying a true cycle exists by running a number of steps equal to the cycle length. Is the reason we don't do that that the probability is so low from what we can tell?

How big is this units digit you mention; the rightmost 1 bit? 4 bits? 64 bits?
See https://www.mersenneforum.org/showpo...1&postcount=10

[JuanTutors]

Originally Posted by kriesel

How big is this units digit you mention; the rightmost 1 bit? 4 bits? 64 bits?
See https://www.mersenneforum.org/showpo...1&postcount=10

I just mean the last bit, stored locally. For an n-digit mersennes, the file would be n bits large, and does not need to be uploaded. Quick math says the probability of a cycle existing is approximately p/Mp if the residues are distributed randomly within the range [0,Mp-1]. I'm not saying that number isn't exceedingly small if the residues are in fact randomly distributed. My question is partially asking whether the question about cycles existing is open, and partially about whether the cost is close to zero enough that it's interesting to try to answer.

[LaurV]

Originally Posted by dominicanpapi82

in less than 1 second

Do you mean like 330 times slower than the LL test itself is done?
(Think about the fact that each iteration takes, say, 3 milliseconds, in an average processor, for an average exponent.)

Joking apart, and from mathematical point of view, the length of a cycle would be closely related to the znorder of the factors. And smallest factors are larger than the exponent, by at least a factor of 2 (for p=4k+3) or 6 (for p=4k+1). If m turns out prime, there are no cycles (beside of the trivial 2-2-2-2-2). For composites, possible cycles are larger than the number of iterations we do. We'll never find one... (even the trivial cycle for a prime, happens AFTER the test is finished)

[JuanTutors]

Originally Posted by LaurV

Do you mean like 330 times slower than the LL test itself is done?

(Think about the fact that each iteration takes, say, 3 milliseconds, in an average processor, for an average exponent.)

True! Perhaps much faster than that. And looking for a cycle is probably significantly faster than looking for other things. Nearly free, except for the fact that the string has to be stored, so it does take SOME memory and circles per iteration. Really depends on how useful or interesting the question is. I would estimate that it would add perhaps a minute per LL test based on absolutely nothing.