mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Miscellaneous Math

Reply
 
Thread Tools
Old 2014-12-09, 11:00   #1
primus
 
Jul 2014
Montenegro

2·13 Posts
Default 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}
primus is offline   Reply With Quote
Old 2014-12-14, 11:22   #2
davar55
 
davar55's Avatar
 
May 2004
New York City

108B16 Posts
Default

Quote:
Originally Posted by primus View Post
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}
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?
davar55 is offline   Reply With Quote
Old 2014-12-14, 14:24   #3
primus
 
Jul 2014
Montenegro

2×13 Posts
Default

Finding the starting value .
primus is offline   Reply With Quote
Old 2014-12-14, 15:53   #4
davar55
 
davar55's Avatar
 
May 2004
New York City

5·7·112 Posts
Default

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.
davar55 is offline   Reply With Quote
Old 2014-12-14, 17:28   #5
primus
 
Jul 2014
Montenegro

2·13 Posts
Default

Quote:
Originally Posted by davar55 View Post
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 .
primus is offline   Reply With Quote
Old 2014-12-14, 19:02   #6
davar55
 
davar55's Avatar
 
May 2004
New York City

108B16 Posts
Default

Where does 5778 come from as initiator?

How is the fact that 5778 = 76^2 + 2 relevant?
davar55 is offline   Reply With Quote
Old 2014-12-16, 08:54   #7
primus
 
Jul 2014
Montenegro

2·13 Posts
Default

Quote:
Originally Posted by davar55 View Post
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.
primus is offline   Reply With Quote
Old 2014-12-16, 16:11   #8
davar55
 
davar55's Avatar
 
May 2004
New York City

5·7·112 Posts
Default

Quote:
Originally Posted by primus View Post
Reference :

D. H. Lehmer, "An extended theory of Lucas' functions," Ann. of Math., v. 31, 1930, pp.419-448.
OK Thanks.
davar55 is offline   Reply With Quote
Old 2015-03-18, 13:06   #9
primus
 
Jul 2014
Montenegro

2610 Posts
Default

Quote:
Originally Posted by davar55 View Post

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}<br />
		k\equiv 3 \pmod{30}\text{~ with ~} b \equiv 2 \pmod{10}\text{~ and ~ }n \equiv 0,3 \pmod{4} \\<br />
		k\equiv 3 \pmod{30}\text{~ with ~} b \equiv 4 \pmod{10}\text{~ and ~ } n \equiv 0,2 \pmod{4} \\<br />
		k\equiv 3 \pmod{30}\text{~ with ~}b \equiv 6 \pmod{10}\text{~ and ~ }n \equiv 0,1,2,3 \pmod{4} \\<br />
		k\equiv 3 \pmod{30}\text{~ with ~}b \equiv 8 \pmod{10}\text{~ and ~ }n \equiv 0,1 \pmod{4}<br />
		\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}
primus is offline   Reply With Quote
Old 2015-03-18, 16:20   #10
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

960810 Posts
Default

Quote:
Originally Posted by primus View Post
...{~ and ~ }n \equiv 0,1,2,3 \pmod{4}
A very important condition, that one.
Batalov is offline   Reply With Quote
Old 2015-03-18, 21:45   #11
ewmayer
2ω=0
 
ewmayer's Avatar
 
Sep 2002
Rep├║blica de California

32·1,297 Posts
Default

Quote:
Originally Posted by Batalov View Post
A very important condition, that one.
Really winnows the possibilities, don't it?
ewmayer is offline   Reply With Quote
Reply

Thread Tools


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

All times are UTC. The time now is 09:10.


Sun Nov 28 09:10:45 UTC 2021 up 128 days, 3:39, 0 users, load averages: 0.74, 0.92, 0.90

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