Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [lucas-lehmer-test]

The tag has no usage guidance.

3
votes
1answer
335 views

Primality test for numbers of the form $N=4 \cdot 3^n+1$

Can you provide proof or counterexample for the claim given below? Inspired by Lucas-Lehmer primality test I have formulated the following claim: Let $P_m(x)=2^{-m}\cdot((x-\sqrt{x^2-4})^m+(x+\...
5
votes
1answer
346 views

Primality test for numbers of the form $N=4 \cdot 3^n-1$

Can you provide proof or counterexample for the claim given below? Inspired by Lucas-Lehmer primality test I have formulated the following claim: Let $P_m(x)=2^{-m}\cdot((x-\sqrt{x^2-4})^m+(x+\...
8
votes
1answer
399 views

Primality test for numbers of the form $N=k \cdot 3^n-1$

Can you provide proof or counterexample for the claim given below? Inspired by Lucas-Lehmer-Riesel primality test I have formulated the following claim: Let $P_m(x)=2^{-m}\cdot((x-\sqrt{x^2-4})^m+(...
2
votes
1answer
64 views

Primality test for Mersenne numbers using the fourth Chebyshev polynomial of the first kind

Can you provide a proof or a counterexample for the claim given below? Inspired by Lucas-Lehmer test I have formulated the following claim : Let $T_n(x)$ be the nth Chebyshev polynomial of the ...
5
votes
1answer
458 views

Conjectured primality tests for specific classes of $k\cdot b^n \pm 1$

Can you provide proofs or counterexamples for the claims given below? Inspired by Lucas-Lehmer-Riesel primality test I have formulated the following two claims: First claim Let $P_m(x)=2^{-m}\...
2
votes
1answer
136 views

Lucas Lehmer Test

I have tried to write a function that test if it is prime using Lucas Lehmer Test ...
1
vote
0answers
46 views

Pell-Lucas number

I'm studying about Pell number and Pell-Lucas number whose have Binet formula $P_n=\frac{\alpha^n-\beta^n}{\alpha-\beta}$ and $Q_n=\alpha^n+\beta^n$, where $\alpha=1+\sqrt{2}$ and $\beta=1-\sqrt{2}$, ...
1
vote
0answers
71 views

What are some basic properties of the quotient $s_n\over M_p$ where $M_p$ is a Mersenne prime?

I've been exploring the Lucas-Lehmer test for a while now. I already know the square of one Mersenne $(2^n-1)^2$ is $(2^{n-1}-1)(2^{n+1}-1)+2^{n-1}$. Today I'm looking to use the properties of the ...
2
votes
2answers
92 views

What area's of mathematics are needed to make a basic understanding of the FFT algorithm ?

I know FFT is used in signal processing ( at last check), the Lucas-Lehmer Test and probably many other things. But what is the Fast Fourier Transform and what area's of math will help me understand ...
-1
votes
2answers
131 views

Are there other ways of doing the Lucas -Lehmer primality test other than this?

The usual ( but simple version) Lucas-Lehmer primality test, as done on Mersenne numbers ( of form $2^n-1$) is as follows: $$s_0=4\\s_n=(s_{n-1})^2-2 \pmod {2^n-1}\\if\;s_{p-2}\equiv0\pmod{2^n-1}\\2^...
0
votes
0answers
52 views

What is the easiest non FFT simplification, of this alternate Lucas-Lehmer test ( from a mathematical standpoint)?

We start, with the original Lucas-Lehmer test format: $s_0=4\\ s_i=s_{i-1}^2-2 \pmod {2^p-1}$ We can note, right away, that all terms are even. Dividing out the factor of 2, we get: $s_0=2\\ s_i=...