 mersenneforum.org > Math Rotating the Initial Start Value Of a LL Test
 Register FAQ Search Today's Posts Mark Forums Read 2004-08-24, 04:38 #1 dave_0273   Oct 2003 Australia, Brisbane 47010 Posts 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??   2004-08-24, 10:11 #2 T.Rex   Feb 2004 France 13·73 Posts 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   2004-08-24, 16:20 #3 nfortino   Nov 2003 3×5×11 Posts 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.   2004-08-24, 23:08 #4 dave_0273   Oct 2003 Australia, Brisbane 2×5×47 Posts 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.   2004-08-25, 07:22   #5
T.Rex

Feb 2004
France

13·73 Posts 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    2004-08-25, 07:35 #6 TTn   313010 Posts 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  2004-08-25, 07:55 #7 TTn   71716 Posts 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...   2004-08-25, 16:18 #8 nfortino   Nov 2003 A516 Posts 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.   2004-08-25, 17:41 #9 akruppa   "Nancy" Aug 2002 Alexandria 2,467 Posts 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   2004-08-25, 18:24 #10 TTn   135710 Posts TTn Different track, same train. Thread Tools Show Printable Version Email this Page Similar Threads Thread Thread Starter Forum Replies Last Post RMSe17 Information & Answers 2 2014-12-16 18:55 nisko Information & Answers 5 2013-06-22 05:10 marks9GIMPS Information & Answers 5 2011-06-05 18:44 davieddy Puzzles 7 2008-04-09 01:12 E_tron Software 2 2004-05-20 13:27

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

Sun Oct 1 17:02:42 UTC 2023 up 18 days, 14:45, 0 users, load averages: 0.93, 1.00, 0.96

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.

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