mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math

Reply
 
Thread Tools
Old 2016-01-07, 02:40   #1
CuriousKit
 
"J. Gareth Moreton"
Feb 2015
Nomadic

2·32·5 Posts
Question 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?
CuriousKit is offline   Reply With Quote
Old 2016-01-07, 02:51   #2
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

26×131 Posts
Default

Quote:
Originally Posted by CuriousKit View Post
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
science_man_88 is offline   Reply With Quote
Old 2016-01-07, 07:39   #3
ATH
Einyen
 
ATH's Avatar
 
Dec 2003
Denmark

31·101 Posts
Default

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
ATH is online now   Reply With Quote
Old 2016-01-07, 11:29   #4
CuriousKit
 
"J. Gareth Moreton"
Feb 2015
Nomadic

1328 Posts
Thumbs up

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
CuriousKit is offline   Reply With Quote
Old 2016-01-07, 13:25   #5
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

26·131 Posts
Default

Quote:
Originally Posted by CuriousKit View Post
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
science_man_88 is offline   Reply With Quote
Old 2016-01-07, 17:43   #6
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

2×3×1,571 Posts
Default

Quote:
Originally Posted by CuriousKit View Post
....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...
Batalov is offline   Reply With Quote
Old 2016-01-07, 21:17   #7
CuriousKit
 
"J. Gareth Moreton"
Feb 2015
Nomadic

2×32×5 Posts
Lightbulb

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!
CuriousKit is offline   Reply With Quote
Old 2016-01-29, 13:26   #8
JeppeSN
 
JeppeSN's Avatar
 
"Jeppe"
Jan 2016
Denmark

23×3×7 Posts
Cool

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
JeppeSN is offline   Reply With Quote
Old 2016-01-29, 14:44   #9
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Cambridge (GMT/BST)

16EE16 Posts
Default

Quote:
Originally Posted by JeppeSN View Post
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.
henryzz is online now   Reply With Quote
Old 2016-01-29, 15:11   #10
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

838410 Posts
Default

Quote:
Originally Posted by JeppeSN View Post
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
science_man_88 is offline   Reply With Quote
Old 2016-01-31, 05:39   #11
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

24E516 Posts
Default

No.
There can't be a cycle with the period smaller than 2p.
LaurV is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Timing for different B1 values? CRGreathouse GMP-ECM 8 2018-05-12 05:57
reserving a few k values Trilo Riesel Prime Search 7 2015-09-27 23:20
Erroneous data ATH Data 8 2013-11-13 19:21
reserving a few k values Trilo Riesel Prime Search 0 2013-08-25 14:47
B1/B2 values 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

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, 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.