20200724, 20:10  #1 
"Viliam Furík"
Jul 2018
Martin, Slovakia
2·5·71 Posts 
Repeating residues in LL tests of composite Mersenne numbers
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. 
20200725, 10:00  #2 
"Viliam Furík"
Jul 2018
Martin, Slovakia
2·5·71 Posts 

20200801, 07:52  #3  
"Mihai Preda"
Apr 2015
5^{3}×11 Posts 
Quote:
Last fiddled with by preda on 20200801 at 07:54 

20200802, 09:26  #4 
"Jeppe"
Jan 2016
Denmark
10101111_{2} Posts 
The LL sequence starts 4, 14, 194, ...
Since we calculate modulo 2^p  1, there are only finitely many values we can hit, so sooner or later we are going to hit a value we have seen before. For 2^p  1 prime, we know we hit 0, "2", 2, 2, 2, ... So the period starts late and has length 1. For 2^p  1 composite (p prime), do you know if it is always 14 which is the first term to reappear? How does your script detect that a period has finished (in order to report the period length)? /JeppeSN 
20200802, 12:50  #5 
"Viliam Furík"
Jul 2018
Martin, Slovakia
2×5×71 Posts 
It simply looks for a value 14, based on previous observation, that periodicity starts at first modular squaring (S(1) = 14). But to answer previou question, I don't actually know that for sure, it's just that I haven't found a counterexample yet.

20200802, 18:27  #6 
"Viliam Furík"
Jul 2018
Martin, Slovakia
2C6_{16} Posts 
Python code
My slow but simple Python code in its entirity:
Code:
s = 4 for a in range(2 ** 37 + 1): s = (s ** 2  2) % (2 ** 37  1): if s == 14: print(a) 
20200802, 23:47  #7 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2
9,629 Posts 
Code:
period 60 for M11 period 32340 for M23 period 252 for M29 period 516924 for M37 period 822960 for M41 period 420 for M43 period 20338900 for M47 period 1309620 for M53 period 345603421440 for M59 (period is always a multiple of (p1) ) _____________ main(int argc,char **argv) { uint64_t f,b,c,j,k,l,l2; //... if(argc<=1) { printf(" Use: %s p\n\t (copyleft) 2020 S.Batalov\n",argv[0]); exit(0); } if(argc>1) l = atoll(argv[1]); printf("# %lld ... testing\n",l); l = 1ULL << l; l; c = 4; for(f=1; f<=120000;f++) { # or some other number,  to get into "real" cycle c = mulmod(c,c,l)2; } b = c; c = mulmod(b,b,l)2; for(f=1; c!=b && f<=l;f++) { c = mulmod(c,c,l)2; } printf(" period %lld for M%lld\n",f,atoll(argv[1])); exit(0); } *we all already know that we will never see 4 again, because 6 is a nonresidue. 16 and 196 are residues 
20200803, 07:33  #8 
"Jeppe"
Jan 2016
Denmark
257_{8} Posts 
Thanks, Batalov, that confirms my suspicion. For example for p=37 (the first one Viliam Furik's method failed for), we start with:
4 > 14 > 194 > 37634 > 1416317954 > (period starts here) 111419319480 > ... So in this case, the period starts at the first term after we have "wrapped around" because we work modulo 2^37  1 = 137438953471. /JeppeSN 
20200803, 07:54  #9 
"Viliam Furík"
Jul 2018
Martin, Slovakia
1306_{8} Posts 
Спасибо! But it still leaves the question "Why that period?" hanging in the air...

20200803, 08:35  #10 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2
9,629 Posts 
We had a forum member about a decade ago who drilled into residue pathways/topology/cycles but he has left many years ago and left all that quite unfinished. (Tony "T.Rex")
He had some conjectures but as far as I remember those ended up broken. (Including one about a Wagstaff number test.) One can search forum way back, using Search / Advanced / Search by User Name, and search for his threads, such as DiGraph for LLT, LLT Cycles, LLT Tree... there is probably something of interest (just don't assume those things right ... or wrong), pick and chose what is useful. https://mersenneforum.org/showthread.php?t=5935 https://mersenneforum.org/showthread.php?t=10670 ...and more 
20200803, 16:45  #11  
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2
9,629 Posts 
Quote:
1. residue is in effect a Chinese Remainder of residues mod all factors of these (composite) Mp 2. this is an lcm() of individual periods guided by each factor. Code:
M11 = 23 · 89 M23 = 47 · 178481 M29 = 233 · 1103 · 2089 M37 = 223 · 616318177 M41 = 13367 · 164511353 M43 = 431 · 9719 · 2099863 M47 = 2351 · 4513 · 13264529 M53 = 6361 · 69431 · 20394401 M59 = 179951 · 3203431780337 Periods may (?) be different if we use the other popular seed values S0 = 10, or S0 = 2/3 (mod Mp). 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Factoring composite Mersenne numbers using Pollard Rho  jshort  Factoring  9  20190409 16:34 
question: decidability for quadratic residues modulo a composite  LaurV  Math  18  20170916 14:47 
2 holes in bizarre theorem about composite Mersenne Numbers  wildrabbitt  Math  120  20160929 21:52 
Use Pepin's Tests for proving primality of Mersenne numbers ?  T.Rex  Math  12  20160403 22:27 
Factoring highly composite Mersenne numbers  philmoore  Factoring  21  20041118 20:00 