Lucasian Pseudoprimality Hypothesis for Specific Class of k 2^n-1

primus · 2014-12-09, 11:00

Please delete this post if this generalization is already known .

Definition

Let $P_m(x)=2^{-m}\cdot \left(\left(x-\sqrt{x^2-4}\right)^{m}+\left(x+\sqrt{x^2-4}\right)^{m}\right)$ , where $m$ and $x$ are nonnegative integers .

Corollary

Let $N=k\cdot 2^n-1$ such that $n>2$ , $k>0$ , $3 \mid k$ , $k<2^n$ and

$\begin{cases} k \equiv 1 \pmod{10} ~ \text{with }~ n \equiv 2,3 \pmod{4} \\ k \equiv 3 \pmod{10} ~ \text{with } ~ n \equiv 0,3 \pmod{4} \\ k \equiv 7 \pmod{10} ~ \text{with } ~ n \equiv 1,2 \pmod{4} \\ k \equiv 9 \pmod{10} ~\text{ with }~ n \equiv 0,1 \pmod{4} \end{cases}$

Let $S_i=P_2(S_{i-1})$ with $S_0=P_k(18)$ , thus

$N$ is prime iff $S_{n-2} \equiv 0 \pmod{N}$

davar55 · 2014-12-14, 11:22

Quote:

Originally Posted by primus

Please delete this post if this generalization is already known .

Definition

Let $P_m(x)=2^{-m}\cdot \left(\left(x-\sqrt{x^2-4}\right)^{m}+\left(x+\sqrt{x^2-4}\right)^{m}\right)$ , where $m$ and $x$ are nonnegative integers .

Corollary

Let $N=k\cdot 2^n-1$ such that $n>2$ , $k>0$ , $3 \mid k$ , $k<2^n$ and

$\begin{cases} k \equiv 1 \pmod{10} ~ \text{with }~ n \equiv 2,3 \pmod{4} \\ k \equiv 3 \pmod{10} ~ \text{with } ~ n \equiv 0,3 \pmod{4} \\ k \equiv 7 \pmod{10} ~ \text{with } ~ n \equiv 1,2 \pmod{4} \\ k \equiv 9 \pmod{10} ~\text{ with }~ n \equiv 0,1 \pmod{4} \end{cases}$

Let $S_i=P_2(S_{i-1})$ with $S_0=P_k(18)$ , thus

$N$ is prime iff $S_{n-2} \equiv 0 \pmod{N}$

What does the initializer 18 indicate (as opposed to the 4 in LLT) ?
IOW how does the initiator determine the algorithm, rather than the other way around?

primus · 2014-12-14, 14:24

Finding the starting value .

davar55 · 2014-12-14, 15:53

In deriving this algorithm, how was the initial value (18) determined?
How was 4 (or 10) determined to initiate LLT?

The correctness of the algorithm depends on the math proof that
uses or determines the correct initial value. How is the initial value
related to the moduli?

I'd be interested to know if and how this generalization can be further
generalized, say to numbers of the form k*a^m - 1,
with say k >= 1 and a >= 2 and m >= 2.

primus · 2014-12-14, 17:28

Quote:

Originally Posted by davar55

In deriving this algorithm, how was the initial value (18) determined?

$P_3(x)=5778$
Find $x$ ?

You can find more informations in this article .

davar55 · 2014-12-14, 19:02

Where does 5778 come from as initiator?

How is the fact that 5778 = 76^2 + 2 relevant?

primus · 2014-12-16, 08:54

Quote:

Originally Posted by davar55

Where does 5778 come from as initiator?

Reference :

D. H. Lehmer, "An extended theory of Lucas' functions," Ann. of Math., v. 31, 1930, pp.419-448.

davar55 · 2014-12-16, 16:11

Quote:

Originally Posted by primus

Reference :

D. H. Lehmer, "An extended theory of Lucas' functions," Ann. of Math., v. 31, 1930, pp.419-448.

OK Thanks.

primus · 2015-03-18, 13:06

Quote:

Originally Posted by davar55

I'd be interested to know if and how this generalization can be further
generalized, say to numbers of the form k*a^m - 1,
with say k >= 1 and a >= 2 and m >= 2.

Let $P_m(x)=2^{-m}\cdot \left(\left(x-\sqrt{x^2-4}\right)^{m}+\left(x+\sqrt{x^2-4}\right)^{m}\right)$ , where $m$ and $x$ are nonnegative integers .

Let $N=k\cdot b^n-1$ such that $n>2$ , $k<b^n$ and

$\begin{cases} k\equiv 3 \pmod{30}\text{~ with ~} b \equiv 2 \pmod{10}\text{~ and ~ }n \equiv 0,3 \pmod{4} \\ k\equiv 3 \pmod{30}\text{~ with ~} b \equiv 4 \pmod{10}\text{~ and ~ } n \equiv 0,2 \pmod{4} \\ k\equiv 3 \pmod{30}\text{~ with ~}b \equiv 6 \pmod{10}\text{~ and ~ }n \equiv 0,1,2,3 \pmod{4} \\ k\equiv 3 \pmod{30}\text{~ with ~}b \equiv 8 \pmod{10}\text{~ and ~ }n \equiv 0,1 \pmod{4} \end{cases}$

Let $S_i=P_b(S_{i-1})$ with $S_0=P_{bk/2}(P_{b/2}(18))$ , then

$N$ is prime iff $S_{n-2} \equiv 0 \pmod{N}$

Batalov · 2015-03-18, 16:20

Quote:

Originally Posted by primus

$...{~ and ~ }n \equiv 0,1,2,3 \pmod{4}$

A very important condition, that one.

ewmayer · 2015-03-18, 21:45

Quote:

Originally Posted by Batalov

A very important condition, that one.

Really winnows the possibilities, don't it?

2014-12-09, 11:00	#1
primus Jul 2014 Montenegro 32₈ Posts	Lucasian Pseudoprimality Hypothesis for Specific Class of k 2^n-1 Please delete this post if this generalization is already known . Definition Let $P_m(x)=2^{-m}\cdot \left(\left(x-\sqrt{x^2-4}\right)^{m}+\left(x+\sqrt{x^2-4}\right)^{m}\right)$ , where $m$ and $x$ are nonnegative integers . Corollary Let $N=k\cdot 2^n-1$ such that $n>2$ , $k>0$ , $3 \mid k$ , $k<2^n$ and $\begin{cases}<br /> k \equiv 1 \pmod{10} ~ \text{with }~ n \equiv 2,3 \pmod{4} \\<br /> k \equiv 3 \pmod{10} ~ \text{with } ~ n \equiv 0,3 \pmod{4} \\<br /> k \equiv 7 \pmod{10} ~ \text{with } ~ n \equiv 1,2 \pmod{4} \\<br /> k \equiv 9 \pmod{10} ~\text{ with }~ n \equiv 0,1 \pmod{4}<br /> \end{cases}$ Let $S_i=P_2(S_{i-1})$ with $S_0=P_k(18)$ , thus $N$ is prime iff $S_{n-2} \equiv 0 \pmod{N}$

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Pseudoprimality Hypothesis for Specific Class of Generalized Fermat Numbers	primus	Miscellaneous Math	1	2015-03-25 22:18
Conjectured Primality Test for Specific Class of Mersenne Numbers	primus	Miscellaneous Math	1	2014-10-12 09:25
Disproven Primality Test for Specific Class of kb^n-1	primus	Computer Science & Computational Number Theory	8	2014-08-21 15:16
Conjectured Primality Test for Specific Class of k6^n-1	primus	Computer Science & Computational Number Theory	16	2014-08-15 01:15
Lucasian Criteria for the Primality of 2^n+3	princeps	Math	4	2012-04-10 20:08

2014-12-14, 14:24	#3
primus Jul 2014 Montenegro 26₁₀ Posts	Finding the starting value .

2014-12-14, 15:53	#4
davar55 May 2004 New York City 5×7×11² Posts	In deriving this algorithm, how was the initial value (18) determined? How was 4 (or 10) determined to initiate LLT? The correctness of the algorithm depends on the math proof that uses or determines the correct initial value. How is the initial value related to the moduli? I'd be interested to know if and how this generalization can be further generalized, say to numbers of the form k*a^m - 1, with say k >= 1 and a >= 2 and m >= 2.

2014-12-14, 19:02	#6
davar55 May 2004 New York City 1000010001011₂ Posts	Where does 5778 come from as initiator? How is the fact that 5778 = 76^2 + 2 relevant?