mersenneforum.org Conjectured Primality Test for Specific Class of Mersenne Numbers
 User Name Remember Me? Password
 Register FAQ Search Today's Posts Mark Forums Read

 2014-10-12, 09:10 #1 primus   Jul 2014 Montenegro 2·13 Posts Conjectured Primality Test for Specific Class of Mersenne Numbers Conjecture Let $M_p=2^p-1$ such that $p$ is prime and $p\equiv 5 \pmod{6}$ Let $S_i=S_{i-1}^8-8\cdot S_{i-1}^6+20\cdot S_{i-1}^4-16 \cdot S_{i-1}^2+2$ with $S_0=4$ , then $M_p$ is prime iff $S_{(p-2)/3} \equiv 0 \pmod{M_p}$ Maxima Implementations LL Test Code: p:9689; (s:4,M:2^p-1, for i from 1 thru (p-2) do (s:mod(s^2-2,M)))$(if(s=0) then print("prime") else print("composite")); Conjecture Code: p:9689; (s:4,M:2^p-1, for i from 1 thru (p-2)/3 do (s:mod(s^8-8*s^6+20*s^4-16*s^2+2,M)))$ (if(s=0) then print("prime") else print("composite")); Maxima implementation of this modified test is approximately two times faster than Maxima implementation of original Lucas-Lehmer test . Maybe someone on this forum can prove or disprove this conjecture .
2014-10-12, 09:25   #2
axn

Jun 2003

2·2,719 Posts

Quote:
 Originally Posted by primus Maybe someone on this forum can prove or disprove this conjecture .
This isn't a new test. This is just the LL-test, disguised by using a polynomial which combines 3 iterations of LL into 1. It is only faster because of the interpreted nature of your implementation. I'm betting that the plain version will be faster for larger p (because 3 iterations of s^2-2 should be faster than the deg-8 poly).

EDIT:-
Code:
LL1(p)={my(s=Mod(4,2^p-1)); for(i=1,p-2, s=s^2-2); s==0}
LL2(p)={my(s=Mod(4,2^p-1)); for(i=1,(p-2)/3, s=s^8-8*s^6+20*s^4-16*s^2+2); s==0}
LL3(p)={my(s=Mod(4,2^p-1)); for(i=1,(p-2)/3, s=((s^2-2)^2-2)^2-2); s==0}
LL1(9689)
time = 1,280 ms.
LL2(9689)
time = 3,511 ms.
LL3(9689)
time = 1,276 ms.
In PARI/GP, your version is nearly 3 times slower.

Last fiddled with by axn on 2014-10-12 at 09:31

 Similar Threads Thread Thread Starter Forum Replies Last Post primus Miscellaneous Math 14 2015-07-04 15:42 primus Miscellaneous Math 1 2015-03-25 22:18 primus Computer Science & Computational Number Theory 8 2014-08-21 15:16 primus Computer Science & Computational Number Theory 16 2014-08-15 01:15 T.Rex Math 75 2007-09-04 07:53

All times are UTC. The time now is 07:27.

Sun Feb 5 07:27:35 UTC 2023 up 171 days, 4:56, 1 user, load averages: 1.41, 1.09, 1.04

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.

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