mersenneforum.org > Math Erroneous values of s_n?
 Register FAQ Search Today's Posts Mark Forums Read

 2016-01-07, 02:40 #1 CuriousKit   "J. Gareth Moreton" Feb 2015 Nomadic 2·32·5 Posts Erroneous values of s_n? Just to clarify, I'm referring to the value of 'sn' that is calculated in each iteration of the Lucas-Lehmer Primality Test (and which sp-2 mod 264 is the residue stored in the GIMPS database). Mostly out of curiosity but also for mathematics and programming practice, I'm analysing the algorithm used to test Mersenne numbers, but it got me thinking, just from logical reasoning: There seem to be certain values of sn (mod 2p - 1) that, if they appear, indicate a composite Mersenne number at best or an error of some kind at worst: 4 (when n != 0) - if reproducible, the residues form a sequence of period n, and the final residue, which is definitely not zero, can be deduced without actually completing all the iterations, as sp-2 = s(p-2) [B]mod[/B] n. 2 - sn+1 will also equal 2 as a result, and by induction will never leave this value. 1 - next value is -1, which never changes. -1 (or 2p - 2) - as with 2, this value never changes in subsequent iterations. -2 (or 2p - 3) - next value is 2, which never changes. 0 (if n != p - 2) - next value is -2, which in turn becomes 2 and then never changes. Maybe I'm over-thinking this, but do these values ever appear in practice, either as a hardware/mathematical error or as part of a sequence, and if so, how should they be handled?
2016-01-07, 02:51   #2
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

26×131 Posts

Quote:
 Originally Posted by CuriousKit Just to clarify, I'm referring to the value of 'sn' that is calculated in each iteration of the Lucas-Lehmer Primality Test (and which sp-2 mod 264 is the residue stored in the GIMPS database). Mostly out of curiosity but also for mathematics and programming practice, I'm analysing the algorithm used to test Mersenne numbers, but it got me thinking, just from logical reasoning: There seem to be certain values of sn (mod 2p - 1) that, if they appear, indicate a composite Mersenne number at best or an error of some kind at worst: 4 (when n != 0) - if reproducible, the residues form a sequence of period n, and the final residue, which is definitely not zero, can be deduced without actually completing all the iterations, as sp-2 = s(p-2) [B]mod[/B] n. 2 - sn+1 will also equal 2 as a result, and by induction will never leave this value. 1 - next value is -1, which never changes. -1 (or 2p - 2) - as with 2, this value never changes in subsequent iterations. -2 (or 2p - 3) - next value is 2, which never changes. 0 (if n != p - 2) - next value is -2, which in turn becomes 2 and then never changes. Maybe I'm over-thinking this, but do these values ever appear in practice, either as a hardware/mathematical error or as part of a sequence, and if so, how should they be handled?
the case of 4 can be technically any value the sequence takes on that will get that behaviour in theory as the value squared mod the mersenne number then mod 2^64 has either already appeared or the test functions as normal. but that's harder to code efficiently for than the cases of -1,2,and 4 sometimes checking is the inefficient way to code it because if the check takes more time than is needed to complete the test then it becomes faster to complete the test anyways and throw an error at the end I think, but I'm not sure how it's coded for GIMPS. someone more knowledgeable will come along soon I bet. edit: squared minus 2

Last fiddled with by science_man_88 on 2016-01-07 at 03:18

 2016-01-07, 07:39 #3 ATH Einyen     Dec 2003 Denmark 31·101 Posts The residue 2 has happened several times when the partial residue during the run turns to 0 due to a hardware error then it will go 0, -2, 2, 2, 2... and end in 2. Here is one example: http://mersenne.org/M38273689 Here is most likely another 2 that has not been verified yet: http://mersenne.org/M79060367
 2016-01-07, 11:29 #4 CuriousKit   "J. Gareth Moreton" Feb 2015 Nomadic 1328 Posts I can see how checking the value of sn during every iteration is cost-prohibitive, but would it be an idea to check for a value of 2 and -1 every so often, like how rounding is currently performed? It might save some wasted testing (and mark the result as Suspect after it attempts to go back to correct itself)? I assume there haven't been any cases where a residue of 2 is reproducible and verified yet. sn = 4 I can see not being an error, but a special situation of the primality test. I would like to find an example where it appears in practice though. Last fiddled with by CuriousKit on 2016-01-07 at 11:29
2016-01-07, 13:25   #5
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

26·131 Posts

Quote:
 Originally Posted by CuriousKit sn = 4 I can see not being an error, but a special situation of the primality test. I would like to find an example where it appears in practice though.
okay all mersenne numbers with odd exponents>1 fall into 7 or 31 mod 120 and all values in A003010>14 fall into 74 mod 120. 120*x+74 only has remainder 4 by 120*y+31 for x=(10*y+2) mod 120*y+31 and for 120*y+7 for y=0;x=7 but for y>0; x=10*y mod (120*y+7) from what I've tested. now it's as simple as finding the values x takes on in A003010 and you'll have your case. edit: okay technically you need to know the y values mersennes take on as well but both are relatively simple at last check then it's just checking for a conditions.

Last fiddled with by science_man_88 on 2016-01-07 at 13:42

2016-01-07, 17:43   #6
Batalov

"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

2×3×1,571 Posts

Quote:
 Originally Posted by CuriousKit ....an error of some kind at worst:
• 4 (when n != 0) :
cannot be in sequence, because there is no sn-1 such that sn-12 = 6; 6 is QNR (quadratic non-residue).
• same is true for all 3*2n-2 (OEIS seq A033484 ): 1, 4, 10, 22, 46, 94, 190, 382, 766, ...
• But not only these values: Any 3odd*2n-2 also can never be a member of the sequence
• Any K*2n-2, where K=75, 91, 147, 363...

 2016-01-07, 21:17 #7 CuriousKit   "J. Gareth Moreton" Feb 2015 Nomadic 2×32×5 Posts Fascinating. Thanks for the heads-up. I had a feeling quadratic residues/non-residues had something to do with it. Sorry for the naïve question, but how is K defined here? I can see that 75, 147 and 363 are equal to 3 * a prime square, but 91 is an odd one out here. I'm trying to figure out in my head what stops -2, 0 (when n < p - 2) and 2 from appearing. I'm assuming that, for 2, the only values that equate to it are -2 and 2 itself, and 0 is what creates -2 (and I think this is the only value because the only solution to "sn2 ≡ 0 (mod 2p - 1)" is zero, since the modulus cannot be a perfect square). I swear I could go insane trying to get my head around all of this, but I'm going to try!
 2016-01-29, 13:26 #8 JeppeSN     "Jeppe" Jan 2016 Denmark 23×3×7 Posts Let $p$ be an odd prime ($M=2^p-1$ is possibly composite), and $s_n$ be defined as above. If we consider the infinite sequence: $$s_0 \mapsto s_1 \mapsto s_2 \mapsto s_3 \mapsto \dots \pmod{2^p-1}$$ then clearly it will become periodic at one point. For there are only finitely many possible values in $\mathbb{Z}/M\mathbb{Z}$, and as soon as we hit a value we have seen before, we go into a loop. So the question is if it can ever happen for some rare values of $p$ that this becomes periodic before $s_{p-2}$. So is there any $p$ which admits two indices $0 \le i < j \le p-2$ such that $s_i \equiv s_j \pmod{2^p-1}$? Can anybody answer that? /JeppeSN
2016-01-29, 14:44   #9
henryzz
Just call me Henry

"David"
Sep 2007
Cambridge (GMT/BST)

16EE16 Posts

Quote:
 Originally Posted by JeppeSN Let $p$ be an odd prime ($M=2^p-1$ is possibly composite), and $s_n$ be defined as above. If we consider the infinite sequence: $$s_0 \mapsto s_1 \mapsto s_2 \mapsto s_3 \mapsto \dots \pmod{2^p-1}$$ then clearly it will become periodic at one point. For there are only finitely many possible values in $\mathbb{Z}/M\mathbb{Z}$, and as soon as we hit a value we have seen before, we go into a loop. So the question is if it can ever happen for some rare values of $p$ that this becomes periodic before $s_{p-2}$. So is there any $p$ which admits two indices $0 \le i < j \le p-2$ such that $s_i \equiv s_j \pmod{2^p-1}$? Can anybody answer that? /JeppeSN
I pretty certain not if it is a Mersenne prime.

2016-01-29, 15:11   #10
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

838410 Posts

Quote:
 Originally Posted by JeppeSN Let $p$ be an odd prime ($M=2^p-1$ is possibly composite), and $s_n$ be defined as above. If we consider the infinite sequence: $$s_0 \mapsto s_1 \mapsto s_2 \mapsto s_3 \mapsto \dots \pmod{2^p-1}$$ then clearly it will become periodic at one point. For there are only finitely many possible values in $\mathbb{Z}/M\mathbb{Z}$, and as soon as we hit a value we have seen before, we go into a loop. So the question is if it can ever happen for some rare values of $p$ that this becomes periodic before $s_{p-2}$. So is there any $p$ which admits two indices $0 \le i < j \le p-2$ such that $s_i \equiv s_j \pmod{2^p-1}$? Can anybody answer that? /JeppeSN
well if it doesn't loop back to 4 that means k*Mp is the difference of two squares aka it can be expressed as $a^2-b^2$ which if I remember correctly from fermat's method means it can be factored into (a-b)(a+b) so one of these two has to divide by the mersenne number or one of it's factors itself. the other cases are if it loops back to 4, and when it goes to one of the values listed in which case it goes to repeat again and again with period 1. I'm not smart enough to go further into this so I'll leave the rest to someone smarter.

Last fiddled with by science_man_88 on 2016-01-29 at 15:15

 2016-01-31, 05:39 #11 LaurV Romulan Interpreter     Jun 2011 Thailand 24E516 Posts No. There can't be a cycle with the period smaller than 2p.

 Similar Threads Thread Thread Starter Forum Replies Last Post CRGreathouse GMP-ECM 8 2018-05-12 05:57 Trilo Riesel Prime Search 7 2015-09-27 23:20 ATH Data 8 2013-11-13 19:21 Trilo Riesel Prime Search 0 2013-08-25 14:47 esakertt Information & Answers 2 2012-11-14 13:11

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

Wed May 12 14:36:47 UTC 2021 up 34 days, 9:17, 0 users, load averages: 3.09, 3.57, 3.37