Conjectured Primality Test for 2^p-1, (2^p+1)/3 and (2^2^n+1) - Page 2

T.Rex · 2006-05-09, 16:51

Quote:

Originally Posted by bearnol

??
J

Sorry, I've made the mistake to talk about two things in this thread.
My answer: "q=5: S0=16 -> 6 -> 3 -> 7 -> 16 ..." dealt with the conjecture (appearing first in post #1) : a LLT-like test based on LLT-Cycles instead of LLT-Tree. This conjecture is aimed to show that we can get useful properties from the LLT-Cycles. Then, the next step is to use the Cycles of length (q-1)/d with d > 2 , and this is the "idea" I'm talking in the second part of the post #1, which I do not call a conjecture since it is really too "vague" now.
Hope it helps.
T.

T.Rex · 2006-05-09, 17:01

Quote:

Originally Posted by bearnol

btw, the LL test is (very close to) a theoretical maximum of efficiency for any primality test...
J

Yes, I know. My "idea" is not aimed to improve the time required to prove that a Mersenne number is prime. It "only" should speed up the proof that a Mersenne number is NOT prime, for only a subset of Mersenne composites.

Here is the list of Cycles for q=11 and q=23 . One can see that Cycles of length not dividing q-1 do appear, thus reducing the number of "normal" cycles, like cycles of length (q-1)/2 . Also, there are less Cycles than one should expect.

T.

q=11
L : nbre de cycles
1 : 2
2 : 2
3 : 2
4 : 2
5 : 9
10: 1
12: 2
15: 1

q=23
1 : 2
2 : 2
11:15
15:10
22: 1

T.Rex · 2006-05-09, 17:09

Quote:

Originally Posted by ewmayer

Hi, Tony:

I think it would be very useful for you to do an asymptotic-work (and storage) estimation for the cost of *identifying* cycles for large M(p). Knowing that there *exist* cycles for composite M(p) would be of little use if actually ferreting them out proves to be prohibitively expensive in terms of runtime or memory. I'm not sure if Floyd's cycle-finding algorithm is still the state of the art there, but I expect a work estimate based on it would tell us quite a lot.

The idea is not to identify the Cycles of large M(p). As you say, this would be VERY quickly impossible. For the conjecture (a conjecture of LLT-Cycle test equivalent to LLT-Tree test), I've been able to find S0 (3^2+1/3^2) very easily, simply by studying the first q giving a Mersenne prime. About the "idea" splitting the LLT-Cycle test into 2 steps, maybe it is possible to find a formula giving a valid starting S0 for all q. This is done when one uses the LLT for numbers of kind: k.2^q+/-1 (I've forgotten the name of the algorithm, sorry).
Regards,
T.

T.Rex · 2006-05-09, 19:03

Quote:

Originally Posted by T.Rex

... maybe it is possible to find a formula giving a valid starting S0 for all q. This is done when one uses the LLT for numbers of kind: k.2^q-1

It is the Lucas-Lehmer-Riesel (LLR) test where:
$\large S(0) = A^h + A^{-h} \ \text{ and } A =( (a+b \sqrt{D})^2)/r \ , \ Jacobi(D,N) = -1 \text{ and } Jacobi(r,N)*sign(a^2-b^2 D) = -1$ .
See: Maths of LLR
(I would love to get more explanations about this LLR !)

Regards,
T.

bearnol · 2006-05-09, 19:32

Not the first time Shallit has needed correcting...
http://groups.google.com/group/sci.m...9ed82c9f9853e6
J

T.Rex · 2006-05-09, 19:53

Here is the list of Cycles for q=29 :

q=29
L : nbre de cycles
1 : 6
2 : 4
3 : 14
5 : 4
6 : 16
9 : 80
11: 4
12:56
14:328
15: 2
18: 59
20: 4
22: 10
28: 256

For q=11, there is 1 Cycle of length 10 instead of 40 expected if M11 were prime. And there are 9 cycles of length 5 instead of 6 expected.
For q=23, there is 1 Cycle of length 22 instead of 95232 expected if M23 were prime. And there are 15 cycles of length 11 instead of 186 expected.
For q=29, there are 256 Cycles of length 28 instead of 4792905 expected if M29 were prime. And there are 328 cycles of length 14 instead of 1161 expected.

So the probability to reach a Cycle of length (q-1)/2 seems low.

(
Notice that the nodes A of the 6 cycles of length 1 for M29 have the nice property: at least one factor of M29 divides A+1 !
Examples:
A=375579223 factor(A+1)=2^3.233.201491
A=361340596 factor(A+1)=2089.172973
A=336822006 factor(A+1)=1103.305369
)

Regards,

Tony

cheesehead · 2006-05-12, 16:11

Quote:

Originally Posted by bearnol

the LL test is (very close to) a theoretical maximum of efficiency for any primality test...

By efficiency, do you mean the computation time in terms of N? What defines its theoretical maximum?

bearnol · 2006-05-12, 19:27

Yes, 1 modmult for every doubling in size - though of course a 3-PRP followed by LL only if necessary is ever so slightly quicker still...
J

ATH · 2006-05-19, 19:54

Sorry I have a few stupid questions. How do you choose x for the starting S0: S0=3^x+1/3^x ?

And how did you calculate these S0's:
q=5: S0=16
q=7: S0=122
q=11: S0=464
q=13: S0=7290
using S0=(3^2+1/3^2)%M ?

I hope you find someone that can help you prove this, it sounds interesting.

T.Rex · 2006-05-19, 21:36

Quote:

Originally Posted by ATH

Sorry I have a few stupid questions.

I do not think any question is stupid. Asking means you are curious.

Quote:

How do you choose x for the starting S0: S0=3^x+1/3^x ?

Do you mean: how I found that x=2 seems to work for all Mersenne numbers ?
I looked at Cycles generated by q=5, and 7, and I saw that x=2 is the smallest value that works (x must be even) for both 5 and 7, and then I tested for greater q and I saw that it works for q up to M26.

Quote:

And how did you calculate these S0's:
q=5: S0=16
q=7: S0=122
q=11: S0=464
q=13: S0=7290
using S0=(3^2+1/3^2)%M ?

M_q=1+6qk . Thus, even if M_q is not prime, a=(2*M_q+1)/3 exists and is an integer and thus 3*a is equivalent to 1 modulo M_q.
For q=5, 1/3 = (2*31+1)/3 = 21 (mod 31) .
And thus: S_0=3^2+1/3^2 = 9 + 21^2 = 9+7 = 16 (mod 31)

Same for the others. Is it clear now ?

Quote:

I hope you find someone that can help you prove this, it sounds interesting.

Yes, it looks interesting. But there are 2 problems:
- there may exist a q such that S_{q-1} = S_0 (mod M_q) but M_q is not prime. bad.
- the conjecture may be true, but there is no way to prove it. Bad too.
In fact, it is possible that the conjecture can be proven only if one knows many factors of M_q - 1 . Which is a very difficult problem (See the other conjecture about (M_q-1)/order(3,M_q) ) . They are related, probably.

I'm now trying to use Lucas Sequences. Not sure they can prove the conjecture ...
Probably proving this conjecture does require tools from other domains of Mathematic than the usual ones ...

Regards,

Tony

ATH · 2006-05-20, 01:45

Quote:

Do you mean: how I found that x=2 seems to work for all Mersenne numbers ?

Was just wondering why you used x=28 in your q=13 example and x=2 in your first general post. Thanks for the S0 explanation.

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Modifying the Lucas Lehmer Primality Test into a fast test of nothing	Trilo	Miscellaneous Math	25	2018-03-11 23:20
Conjectured Primality Test for Specific Class of Mersenne Numbers	primus	Miscellaneous Math	1	2014-10-12 09:25
Conjectured Primality Test for Specific Class of k6^n-1	primus	Computer Science & Computational Number Theory	16	2014-08-15 01:15
there is another way to test the primality of a no	shawn	Miscellaneous Math	5	2007-07-17 17:55
A primality test for Fermat numbers faster than Pépin's test ?	T.Rex	Math	0	2004-10-26 21:37

2006-05-09, 19:32	#16
bearnol Sep 2005 127₁₀ Posts	Not the first time Shallit has needed correcting... http://groups.google.com/group/sci.m...9ed82c9f9853e6 J

2006-05-09, 19:53	#17
T.Rex Feb 2004 France 1110010100₂ Posts	Here is the list of Cycles for q=29 : q=29 L : nbre de cycles 1 : 6 2 : 4 3 : 14 5 : 4 6 : 16 9 : 80 11: 4 12:56 14:328 15: 2 18: 59 20: 4 22: 10 28: 256 For q=11, there is 1 Cycle of length 10 instead of 40 expected if M11 were prime. And there are 9 cycles of length 5 instead of 6 expected. For q=23, there is 1 Cycle of length 22 instead of 95232 expected if M23 were prime. And there are 15 cycles of length 11 instead of 186 expected. For q=29, there are 256 Cycles of length 28 instead of 4792905 expected if M29 were prime. And there are 328 cycles of length 14 instead of 1161 expected. So the probability to reach a Cycle of length (q-1)/2 seems low. ( Notice that the nodes A of the 6 cycles of length 1 for M29 have the nice property: at least one factor of M29 divides A+1 ! Examples: A=375579223 factor(A+1)=2^3.233.201491 A=361340596 factor(A+1)=2089.172973 A=336822006 factor(A+1)=1103.305369 ) Regards, Tony

2006-05-12, 19:27	#19
bearnol Sep 2005 7F₁₆ Posts	Yes, 1 modmult for every doubling in size - though of course a 3-PRP followed by LL only if necessary is ever so slightly quicker still... J

2006-05-19, 19:54	#20
ATH Einyen Dec 2003 Denmark 3159₁₀ Posts	Sorry I have a few stupid questions. How do you choose x for the starting S0: S0=3^x+1/3^x ? And how did you calculate these S0's: q=5: S0=16 q=7: S0=122 q=11: S0=464 q=13: S0=7290 using S0=(3^2+1/3^2)%M ? I hope you find someone that can help you prove this, it sounds interesting.