mersenneforum.org  

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

Reply
 
Thread Tools
Old 2004-08-24, 04:38   #1
dave_0273
 
dave_0273's Avatar
 
Oct 2003
Australia, Brisbane

2×5×47 Posts
Default Rotating the Initial Start Value Of a LL Test

I am not really sure if this is the right forum, so if it isn't feel free to move it...


I am wondering how the rotating of the initial start value of a LL test works. What I assume that it means is that instead of using S(0)=4 you start with another value.

I tried this on M7 (2^7-1) which is prime. I started with 5, but that didn't give a result of 0. So, I tested some other numbers up to 20. I found the following....

S(0)=3,4,10,18 gave a residue of 0, however the rest of the numbers between 1 and 20 did not.

However, seeing as the residue should be 0 no matter how much you rotate it (or at least that is what I assume), I must be doing something wrong.

Is someone able to point me on the right track please??
dave_0273 is offline   Reply With Quote
Old 2004-08-24, 10:11   #2
T.Rex
 
T.Rex's Avatar
 
Feb 2004
France

3·311 Posts
Default non-residues

Hi,
I don't have the papers with me now, but I think:
You can use values A that are non-residue modulo Mq (that means there is no x such that x^2 - 2 ~= A (mod Mq)). Like 4 and 52 .
There are 2 formula for finding these numbers starting from 4. I don't remember them now ...
Example: q=5 Mq=31 , you can use 4, 9, 10 and 11 (and -4, -9, -10, -11) as starting values for A.
52 = 31 + 21 ~= -10 (mod 31) .
I'll give more info later.
Tony
T.Rex is offline   Reply With Quote
Old 2004-08-24, 16:20   #3
nfortino
 
nfortino's Avatar
 
Nov 2003

3·5·11 Posts
Default

From http://www.mersenne.org/math.htm

GIMPS double-checking goes a bit further to guard against programming errors. Prior to starting the Lucas-Lehmer test, the S0 value is left-shifted by a random amount. Each squaring just doubles how much we have shifted the S value. Note that the mod 2P-1 step merely rotates the p-th bits and above to the least significant bits, so there is no loss of information. Why do we go to this trouble? If there were a bug in the FFT code, then the shifting of the S values ensures that the FFTs in the first primality test are dealing with completely different data than the FFTs in the second primality test. It would be near impossible for a programming bug to produce the same final 64 bit residues.
nfortino is offline   Reply With Quote
Old 2004-08-24, 23:08   #4
dave_0273
 
dave_0273's Avatar
 
Oct 2003
Australia, Brisbane

2×5×47 Posts
Default

T.Rex, if you could get those 2 formulas to me for how to generate the initial values of an LL test, that would be really appreciated.
dave_0273 is offline   Reply With Quote
Old 2004-08-25, 07:22   #5
T.Rex
 
T.Rex's Avatar
 
Feb 2004
France

3·311 Posts
Default The formula.

I found it.

It's: F(x) = x(x^2-3) .
If you compute: x=F(x) (mod Mq) for q=5 and starting with x=4, you get: 4, -10, -9, 11, -4, 10, 9, -11, and 4 again.
Notice that: f(F(x)) = F(f(x)) !!! I think this is very important, but I have no proof and I found no information about it. It's just experimental. I call F the orthogonal function to f.

The other formula are:
"For starting values we can use 4, 52, 724, ..., U{n}, ..., where U{n} = 14*U{n-1} - U{n-2} and 10, 970, 95050, ..., V{n}, ..., where V{n} = 98*V{n-1} - V{n-2}. Also there are 2^(p-2) starting values that depend upon p. For example to test 2^5-1 we could use the starting values 4, 9, 10, 11, 20, 21, 22, or 27."
98 = 14*7 (why ??).
But I don't have the theory explaining that.

Meaning that:
Quote:
f(x) = x^2-2 <==> U{n} =14*U{n-1} - U{n-2}
F(x) = x(x^2-3) <==> V{n} = 98*V{n-1} - V{n-2}
Regards,
Tony
T.Rex is offline   Reply With Quote
Old 2004-08-25, 07:35   #6
TTn
 

35428 Posts
Thumbs up LL start

I just posted this in another forum:

A Mersenne number M(p) is prime if M(p) divides S(p-2) where S(0)=4
and, S(p)=S(p-1)^2 -2(mod 2^p -1)
With S(0)=3, you get my double case test/probable test, where L(n)
are Lucas numbers, via the golden proportion)(10/19/01)
The golden ratio could possibly speed up the squarings involved.
Since there are various algorithmic ways to generate Lucas numbers, by adding fractals etc.
The mod here, would be subracted at each add, rather than divided out.

L(2^(p-1))mod 2^p -1 = 0 [CASE1]
L(2^(p-1) -1) mod 2^p -1 = 0 [CASE2]
Or L(2^(p-1) -1)mod 2^p +1 /3 = 0[CASE2]

2^2-1=3 divides L(2)=3 [C1]
2^3-1=7 divides, L(4)=7 [C1]
2^5-1=31 divides, L(15)=1364 [C2]
2^7-1=127 divides, L(64)=23725150497407 [C1]
2^13-1=8191 divides, L(4095) [C2]
2^17-1=131071 divides, L(65535) [C2]
2^19-1=524287 divides, L(262144) [C1]

So, also with F(n): (Fibonacci numbers)
F(2^p) mod 2^p -1 = 0[Case 1]
F(2^p -2) mod 2^p -1 = 0[Case 2]
Or F(2^p -2) mod 2^p +1 /3 = 0[Case 2]


2^2-1=3 divides F(4)=3 [C1]
2^3-1= 7 divides F(8)=21 [C1]
2^5-1=31 divides F(30)=832040, [C2]
2^7-1=127 divides F(128)=251728825683549488150424261 [C1]
2^13-1=8191 divides F(8190) [C2]
2^17-1=131071 divides F(131070) [C2]
2^19-1=524287 divides F(524288) [C1]


David Broadhurst wrote me:
The classic Lucas-Lehmer test for Mersennes
uses the Lucas sequence with
p=2, q=-2, d=p^2-4*q=12 (Ribenboim p.92).
You can "probably" use the same batch of theorems
from Ribenboim to prove the necessity and sufficiency
of your more complicated two-case test with
p=1, q=-1, d=p^2-q=5 (i.e. the rabbit case).

This is proven completey true up to Lucas# = L(2^4499)
Though, the residue of the Mersenne exponent mod 4, decides whether
or not the test is deterministic.

Last fiddled with by TTn on 2004-08-25 at 07:37
  Reply With Quote
Old 2004-08-25, 07:55   #7
TTn
 

3·7·137 Posts
Lightbulb Implicit

Though this test should never be wrong, otherwise a zeta zero would fall outside the critical strip. I have no proof of this, I just believe...
  Reply With Quote
Old 2004-08-25, 16:18   #8
nfortino
 
nfortino's Avatar
 
Nov 2003

3×5×11 Posts
Default

While the multiple roots of the LL test are very interesting, they are not the answer to Dave's original question (or at least I don't think so). I assume he was asking about how the rotation of the start value is used by prime95. Prime95 left shifts (i.e. multiplies by a power of 2) by a random amount. It is possible to trace the effect of this left shift throughout the test, and undo it at the end, giving the final residue. Using a different root of the LL test cannot be used because it affects the residue in an unpredictable way. While all roots will return 0 if the exponent is prime, they return different non-zero residues if the exponent is not prime. This makes double-checking useless.
nfortino is offline   Reply With Quote
Old 2004-08-25, 17:41   #9
akruppa
 
akruppa's Avatar
 
"Nancy"
Aug 2002
Alexandria

2,467 Posts
Default

Re. Dave's original question:

the subtraction of 2 must be shifted, too. In each iteration, the position of the unit bit doubles (mod p), due to the squaring.

i.e.

(r * 2^s)^2 - 2 * 2^(2s) = (r^2 - 2) * 2^(2s)

Example Pari-GP code:

\\ LL test of 2^p-1, initial value shifted left s positions
LLshift(p,s) =
{
local(i, r, t);
r = 4 * 2^s % (2^p-1);
t = s;
for (i = 1, p-2, t = 2 * t % p; r = (r^2 - 2 * 2^t) % (2^p-1));
return (r * 2^(p - t) % (2^p-1)); \\ Shift right t positions
}


Alex
akruppa is offline   Reply With Quote
Old 2004-08-25, 18:24   #10
TTn
 

2×32×11×43 Posts
Default TTn

Different track, same train.
  Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Prime95 v28.5.1 Error at Torture test start RMSe17 Information & Answers 2 2014-12-16 18:55
How do I start the memory test? nisko Information & Answers 5 2013-06-22 05:10
Can I just start Prime95 by running torture test? marks9GIMPS Information & Answers 5 2011-06-05 18:44
Rotating cylinder davieddy Puzzles 7 2008-04-09 01:12
Making LL test start over E_tron Software 2 2004-05-20 13:27

All times are UTC. The time now is 00:30.


Fri Feb 3 00:30:49 UTC 2023 up 168 days, 21:59, 1 user, load averages: 1.22, 1.03, 0.94

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

≠ ± ∓ ÷ × · − √ ‰ ⊗ ⊕ ⊖ ⊘ ⊙ ≤ ≥ ≦ ≧ ≨ ≩ ≺ ≻ ≼ ≽ ⊏ ⊐ ⊑ ⊒ ² ³ °
∠ ∟ ° ≅ ~ ‖ ⟂ ⫛
≡ ≜ ≈ ∝ ∞ ≪ ≫ ⌊⌋ ⌈⌉ ∘ ∏ ∐ ∑ ∧ ∨ ∩ ∪ ⨀ ⊕ ⊗ 𝖕 𝖖 𝖗 ⊲ ⊳
∅ ∖ ∁ ↦ ↣ ∩ ∪ ⊆ ⊂ ⊄ ⊊ ⊇ ⊃ ⊅ ⊋ ⊖ ∈ ∉ ∋ ∌ ℕ ℤ ℚ ℝ ℂ ℵ ℶ ℷ ℸ 𝓟
¬ ∨ ∧ ⊕ → ← ⇒ ⇐ ⇔ ∀ ∃ ∄ ∴ ∵ ⊤ ⊥ ⊢ ⊨ ⫤ ⊣ … ⋯ ⋮ ⋰ ⋱
∫ ∬ ∭ ∮ ∯ ∰ ∇ ∆ δ ∂ ℱ ℒ ℓ
𝛢𝛼 𝛣𝛽 𝛤𝛾 𝛥𝛿 𝛦𝜀𝜖 𝛧𝜁 𝛨𝜂 𝛩𝜃𝜗 𝛪𝜄 𝛫𝜅 𝛬𝜆 𝛭𝜇 𝛮𝜈 𝛯𝜉 𝛰𝜊 𝛱𝜋 𝛲𝜌 𝛴𝜎𝜍 𝛵𝜏 𝛶𝜐 𝛷𝜙𝜑 𝛸𝜒 𝛹𝜓 𝛺𝜔