mersenneforum.org  

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

Reply
 
Thread Tools
Old 2022-01-10, 11:51   #1
T.Rex
 
T.Rex's Avatar
 
Feb 2004
France

929 Posts
Default Chebyshev polynomials and higher order Lucas Lehmer algorithm by Kok Seng Chu

Hi,
I've found this recent (2021, October 3rd) paper named "CHEBYSHEV POLYNOMIALS AND HIGHER ORDER LUCAS
LEHMER ALGORITHM", by KOK SENG CHUA, based on previous work by Pedja Terzi´c, and talking about the necessity part.
This looks very interesting to me, since it provides a search about generalized Mersennes and the LLT (x^2-2).
However, I've not spent yet enough time to read it, and it's not easy for me to understand it. So, I'd like to get comments from true mathematicians.
https://arxiv.org/pdf/2010.02677.pdf
Regards
T.Rex is offline   Reply With Quote
Old 2022-01-11, 21:40   #2
T.Rex
 
T.Rex's Avatar
 
Feb 2004
France

929 Posts
Default

The formula for Wagstaff numbers seems OK.

With Pari/gp .

Code:
t(q)={w=(2^q+1)/3;S0=4;print("w: ",w);S=S0;for(i=1,q-1,S=Mod(S^2-2,w));s1=lift(Mod(S-5-9,w));s2=lift(Mod(S-5+9,w));print(s1," ",s2)}

? t(11)
w: 683
665 0

? t(13)
w: 2731
0 18

? t(17)
w: 43691
43673 0

? t(19)
w: 174763
0 18

? t(23)
w: 2796203
2796185 0

? t(29)
w: 178956971           Not prime
59834419 59834437

? t(31)
w: 715827883
0 18

? t(37)
w: 45812984491                  Not prime
24875527143 24875527161

? t(41)
w: 733007751851                 Not prime
634893124730 634893124748

? t(43)
w: 2932031007403
0 18

? t(61)
w: 768614336404564651
0 18
T.Rex is offline   Reply With Quote
Old 2022-01-15, 14:44   #3
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

10111000110112 Posts
Default

The sufficiency result (Lemma 2.1) requires a complete factorization of Q + 1 or Q - 1 in order to prove that Q is prime.
Dr Sardonicus is online now   Reply With Quote
Old 2022-06-12, 20:37   #4
kijinSeija
 
Mar 2021
France

468 Posts
Default

I don't know if it's related to this topic but I made some probable primality test for numbers of the forum (a^p-1)/(a-1) and (a^p+1)/(a+1) using Chebyshev polynomials :

but the test isn't perfect and there are some conditions to apply :

- a must not be a perfect power otherwise you can get false positive.
- p must be a prime number >2 otherwise you can "break" the primality test and get false positive

Let $N = \frac{a^p-1}{a-1}$

Let the sequence S_i = 2 \cdot T_{a}(S_{i-1}/2) where T_{n}(x) is the Chebyshev's polynomial of the first kind with $S_0 = p$

$N$ is prime if S_{p} \equiv 2 \cdot T_{a}(p/2) (mod N) or S_{p} \equiv 2 \cdot T_{a-2}(p/2) (mod N)

You can found the test here : https://sagecell.sagemath.org/?z=eJx...yLjgUAARUAuQ==

For $N = \frac{a^p+1}{a+1}$

Let the sequence S_i = 2 \cdot T_{a}(S_{i-1}/2) where T_{n}(x) is the Chebyshev's polynomial of the first kind with $S_0 = p$

$N$ is prime if S_{p} \equiv 2 \cdot T_{a}(p/2) (mod N) or S_{p} \equiv 2 \cdot T_{a+2}(p/2) (mod N)

You can found the test here : https://sagecell.sagemath.org/?z=eJx...yLjgUAARUAuQ==

For the moment I didn't get a counterexample If you found one please tell me.

EDIT : (Second test fails for (a^3+1)/(a+1) apparently where a = 5 and 7)

Last fiddled with by kijinSeija on 2022-06-12 at 21:20
kijinSeija is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Higher order Wierferich prime pairs carpetpool Miscellaneous Math 2 2018-04-15 00:28
Polynomials defining the same field as cyclotomic polynomial order 5 carpetpool carpetpool 0 2017-04-19 20:33
Lucas-Lehmer test Mathsgirl Information & Answers 23 2014-12-10 16:25
Lucas-Lehmer Test storm5510 Math 22 2009-09-24 22:32
Lucas-Lehmer Dougal Information & Answers 9 2009-02-06 10:25

All times are UTC. The time now is 11:43.


Thu Aug 18 11:43:26 UTC 2022 up 9:12, 0 users, load averages: 1.67, 1.30, 1.21

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

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