View Single Post
Old 2020-08-01, 07:52   #3
preda's Avatar
"Mihai Preda"
Apr 2015

1,373 Posts

Originally Posted by Viliam Furik View Post
I have noticed, that when doing LL tests far behind the p-2 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^p-2, 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 maths-grounded could probably easily shed light here.

Last fiddled with by preda on 2020-08-01 at 07:54
preda is offline   Reply With Quote