mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math > Number Theory Discussion Group

Reply
 
Thread Tools
Old 2020-07-24, 20:10   #1
Viliam Furik
 
Jul 2018
Martin, Slovakia

11×13 Posts
Default Repeating residues in LL tests of composite Mersenne numbers

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.
Viliam Furik is offline   Reply With Quote
Old 2020-07-25, 10:00   #2
Viliam Furik
 
Jul 2018
Martin, Slovakia

11·13 Posts
Default

Quote:
Originally Posted by Viliam Furik View Post
...when prime ones hit 0, next iteration yields 2^p-2, and then the residue is 2...
It should be 2^p - 3, or Mp - 2.
Viliam Furik is offline   Reply With Quote
Old 2020-08-01, 07:52   #3
preda
 
preda's Avatar
 
"Mihai Preda"
Apr 2015

1,223 Posts
Default

Quote:
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
Old 2020-08-02, 09:26   #4
JeppeSN
 
JeppeSN's Avatar
 
"Jeppe"
Jan 2016
Denmark

5·31 Posts
Cool

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
JeppeSN is offline   Reply With Quote
Old 2020-08-02, 12:50   #5
Viliam Furik
 
Jul 2018
Martin, Slovakia

11×13 Posts
Default

Quote:
Originally Posted by JeppeSN View Post
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
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.
Viliam Furik is offline   Reply With Quote
Old 2020-08-02, 18:27   #6
Viliam Furik
 
Jul 2018
Martin, Slovakia

11×13 Posts
Default 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)
Viliam Furik is offline   Reply With Quote
Old 2020-08-02, 23:47   #7
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

9,127 Posts
Default

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 (p-1) )
_____________

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);
}
The cycle does not include 4 (of course*), and not 14 or even 194 for larger p values, but we can greedily simply scroll forward "far enough".

*we all already know that we will never see 4 again, because 6 is a nonresidue. 16 and 196 are residues
Batalov is offline   Reply With Quote
Old 2020-08-03, 07:33   #8
JeppeSN
 
JeppeSN's Avatar
 
"Jeppe"
Jan 2016
Denmark

5·31 Posts
Thumbs up

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
JeppeSN is offline   Reply With Quote
Old 2020-08-03, 07:54   #9
Viliam Furik
 
Jul 2018
Martin, Slovakia

11·13 Posts
Default

Quote:
Originally Posted by Batalov View Post
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 (p-1) )
Спасибо! But it still leaves the question "Why that period?" hanging in the air...
Viliam Furik is offline   Reply With Quote
Old 2020-08-03, 08:35   #10
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

9,127 Posts
Default

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
Batalov is offline   Reply With Quote
Old 2020-08-03, 16:45   #11
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

100011101001112 Posts
rolleyes

Quote:
Originally Posted by Viliam Furik View Post
Спасибо! But it still leaves the question "Why that period?" hanging in the air...
Just a wild guess that:
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
Factorizations are individual in each case (but each factor, as well known, has a multiple of (p+1) sitting in it, so this "reduced variety" reverberates through the process and helps lcm to be a multiple of (p-1) for one reason or another.

Periods may (?) be different if we use the other popular seed values S0 = 10, or S0 = 2/3 (mod Mp).
Batalov is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Factoring composite Mersenne numbers using Pollard Rho jshort Factoring 9 2019-04-09 16:34
question: decidability for quadratic residues modulo a composite LaurV Math 18 2017-09-16 14:47
2 holes in bizarre theorem about composite Mersenne Numbers wildrabbitt Math 120 2016-09-29 21:52
Use Pepin's Tests for proving primality of Mersenne numbers ? T.Rex Math 12 2016-04-03 22:27
Factoring highly composite Mersenne numbers philmoore Factoring 21 2004-11-18 20:00

All times are UTC. The time now is 14:02.

Thu Oct 1 14:02:33 UTC 2020 up 21 days, 11:13, 2 users, load averages: 1.97, 1.68, 1.78

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.