Quote:
Originally Posted by Viliam Furik
I have noticed, that when doing LL tests far behind the p2 iteration, residues start to repeat with a certain period. This happens only for composite Mersenne numbers because when prime ones hit 0, next iteration yields 2^p2, and then the residue is 2 all the way up to infinity.
I found periods for four composite Mersenne numbers, using my rather slow Python script:
M11  60 iters
M23  32340 iters
M29  252 iters
M37  ??? iters (did not finish in my patience time)
M41  822960 iters
I wonder what's the reason behind these periods. Is there some formula for them? Can this be used somehow for testing or factoring purposes? Is it even known fact?
My best guess is that it's the number of quadratic residues modulo Mersenne number.

Hi Viliam, I'm by no means an LL expert, and I don't have an answer to your question here. However, I would approach the question by drilling down into one (or a few) mathematical proofs of the LL test, to understand why it works and the underlying mechanics. Might be that what we see is the "multiplicative order" in some group on which LL is based.. anyway somebody more mathsgrounded could probably easily shed light here.