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

T.Rex · 2022-01-10, 11:51

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 · 2022-01-11, 21:40

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

Dr Sardonicus · 2022-01-15, 14:44

The sufficiency result (Lemma 2.1) requires a complete factorization of Q + 1 or Q - 1 in order to prove that Q is prime.

kijinSeija · 2022-06-12, 20:37

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)

2022-01-10, 11:51	#1
T.Rex Feb 2004 France 13·73 Posts	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

2022-06-12, 20:37	#4
kijinSeija Mar 2021 Home 2³×7 Posts	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

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

2022-01-15, 14:44	#3
Dr Sardonicus Feb 2017 Nowhere 3×13×167 Posts	The sufficiency result (Lemma 2.1) requires a complete factorization of Q + 1 or Q - 1 in order to prove that Q is prime.