mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Miscellaneous Math

Reply
 
Thread Tools
Old 2015-09-04, 21:23   #1
T.Rex
 
T.Rex's Avatar
 
Feb 2004
France

911 Posts
Thumbs up Conjectured compositeness tests for N=k⋅2n±c by Predrag

Predrag (not sure he wants his name to appear since he published as "MathBot") has published a question in StackExchange about a set of 4 conjectures he has built dealing with: "Conjectured compositeness tests for N=k⋅2n±c".

What he proposes seems to me already VERY great, since the 4 conjectures cover ALL numbers N=k2^n \pm c, c odd for sure, with simple but powerful definitions using the LLT (S_n \equiv S_{n-1}^2-2 ~ \pmod{N}) but also higher LLT functions (Chebichev) for the seed and for the last term of the sequence, after n-1 iterations.

However, I've shown that the 4 conjectures can be generalized into only ONE conjecture which handles all kinds of these numbers.
I've provided a PARI/gp for finding counter-examples.

For sure, it is ONLY a conjecture. But this conjecture looks really powerful. I'd like to know if someone is aware about such a general conjecture. I should know, but, after years without looking at such research papers, I do not remember. However, as said RDS, I'm not a PhD, so I'd like other people to have a look and add comments.

I've read other papers of Pedrag: he has played first with smaller examples. So, I think he then spent some time for grouping several examples into a greater conjecture. So:1) he made experiments, 2) he generalized his findings in something more general. Good work !

And, for sure, what I published recently was only children' game compared to Predrag's conjectures.

Here is the PARI/gp program I've written based on work of Predrag, with code for searching counter-examples:

Code:
CEk2c(k,c,g)=
{
a=6;
if(c>0,s=1,s=-1;c=-c);
for(n=2*c+1,g,
N=k*2^n+s*c;
e=c%4;
if(e==1,e=1,e=-1);
d=((c-e)%8)/4;
B=((-1)^d)*s;
A=(c-B)/2;
s0=Mod(2*polchebyshev(k,1,a/2),N);
sn=Mod((-1)^d*2*polchebyshev(A,1,a/2),N);
my(s=s0);
for(i=1,n-1,s=Mod(s^2-2,N));
if(s!=sn && isprime(N),print("k: ",k," c: ",c," n: ",n))
)
}

for(k=1,100,for(c=0,50,CEk2c(k,2*c+1,1000)))
for(k=1,100,for(c=0,50,CEk2c(k,-(2*c+1),1000)))
This comes from : Let say: N=k \cdot 2^n + s \cdot c, with: s = \pm 1 and: c = 4 \cdot d ~\pm 1 ~ \pmod 8 with d=0,1. Then last S_i can be defined as only one expression for all 4 conjectures: S_{n-1} = {(-1)}^d \cdot P_{(c - {(-1)^d \cdot s})/2} ~~~~ (6) . That's quite complicated, but that shows that the 4 conjectures come from a single property depending on k and on the internal structure of c.


Here is the final conjecture I've built after grouping Predrag's 4 conjectures all together.
That does not make the task for proving it easier ! But that's so beautiful.
And, for sure, we have the usual question: is this only a PRP tool or a true primality test ?
Anyway, this conjecture shows how powerful are the ideas that Edouard Lucas discovered about 140 years ago. P_2(x) = x^2-2

\text{Let } ~N=k\cdot 2^n+ s \cdot c ~\text{ such that }~ n>2c ,  k>0 , c>0 ~\text{ and }~ s = \pm 1 ~\text{ and }~ c \equiv 4 \cdot d ~ \pm 1 ~ \pmod 8 ~\text{ and }~ d=0,1

\text{Let }~ S_i=P_2(S_{i-1})~ \text{ with } ~ S_0=P_k(6) ~ \text{ , thus: }

\text{If } ~ N ~\text{ is prime then }~ S_{n-1} \equiv {(-1)}^d \cdot P_{(c - {(-1)^d \cdot s})/2} ~~~~ (6) \pmod{N}

Last fiddled with by T.Rex on 2015-09-04 at 21:29
T.Rex is offline   Reply With Quote
Old 2015-09-04, 21:33   #2
T.Rex
 
T.Rex's Avatar
 
Feb 2004
France

911 Posts
Default

Thanks to primus to have warned me about Predrag's publication in StackExchange.
T.Rex is offline   Reply With Quote
Old 2015-09-04, 22:09   #3
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(3,3^1118781+1)/3

5·1,811 Posts
Default

You didn't even consider that they are one and the same?
Batalov is offline   Reply With Quote
Old 2015-09-05, 01:28   #4
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

26×131 Posts
Default

Quote:
Originally Posted by T.Rex View Post
Code:
CEk2c(k,c,g)=
{
a=6;
if(c>0,s=1,s=-1;c=-c);
for(n=2*c+1,g,
N=k*2^n+s*c;
e=c%4;
if(e==1,e=1,e=-1);
d=((c-e)%8)/4;
B=((-1)^d)*s;
A=(c-B)/2;
s0=Mod(2*polchebyshev(k,1,a/2),N);
sn=Mod((-1)^d*2*polchebyshev(A,1,a/2),N);
my(s=s0);
for(i=1,n-1,s=Mod(s^2-2,N));
if(s!=sn && isprime(N),print("k: ",k," c: ",c," n: ",n))
)
}

for(k=1,100,for(c=0,50,CEk2c(k,2*c+1,1000)))
for(k=1,100,for(c=0,50,CEk2c(k,-(2*c+1),1000)))
thinking about what might speed this up I found ( I'll see which one is faster and none of this uses modern PARI/gp to my knowledge if I realized which one's I could put in parallel I might be able to see if I can speed it up more.

Code:
CEk2c(k,c,g)=
{
a=6;
h=a/2;
if(c>0,s=1,s=-1;c*=-1);
for(n=c<<1+1,g,
N=k<<n+s*c;
e=c%4;
if(e==1,,e=-1);
d=((c-e)%8)/4;
f=((-1)^d)
B=f*s;
A=(c-B)/2;
s0=Mod(polchebyshev(k,1,h)<<1,N);
sn=Mod(f*polchebyshev(A,1,h)<<1,N);
my(s=s0);
forstep(i=n,2,-1,s=sqr(s)-2);
if(s!=sn && isprime(N),print("k: ",k," c: ",c," n: ",n))
)
}

for(k=1,100,for(c=0,50,CEk2c(k,2*c+1,1000)))
for(k=1,100,for(c=0,50,CEk2c(k,-(2*c+1),1000)))
science_man_88 is offline   Reply With Quote
Old 2015-09-05, 10:26   #5
T.Rex
 
T.Rex's Avatar
 
Feb 2004
France

911 Posts
Default

Quote:
Originally Posted by Batalov View Post
You didn't even consider that they are one and the same?
Ha ha ha ! No ! ;) I should have considered... but too busy with other stuff.
T.Rex is offline   Reply With Quote
Old 2015-09-05, 10:30   #6
T.Rex
 
T.Rex's Avatar
 
Feb 2004
France

911 Posts
Default

Quote:
Originally Posted by science_man_88 View Post
thinking about what might speed this up I found ( I'll see which one is faster and none of this uses modern PARI/gp to my knowledge if I realized which one's I could put in parallel I might be able to see if I can speed it up more.
Code:
CEk2c(k,c,g)={ ... forstep(i=n,2,-1,s=sqr(s)-2); ... ) }
I do not think that this will speed up the computation, since PARI goes in Stack overflow quickly. Modulo helps to keep s small.
T.Rex is offline   Reply With Quote
Old 2015-09-05, 12:23   #7
axn
 
axn's Avatar
 
Jun 2003

11×421 Posts
Default

Quote:
Originally Posted by T.Rex View Post
I do not think that this will speed up the computation, since PARI goes in Stack overflow quickly. Modulo helps to keep s small.
The s variable is a Mod() object. All operations with it will automatically work modulo N.
axn is offline   Reply With Quote
Old 2015-09-05, 13:40   #8
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

100000110000002 Posts
Default

Quote:
Originally Posted by T.Rex View Post
I do not think that this will speed up the computation, since PARI goes in Stack overflow quickly. Modulo helps to keep s small.
you can change how much it has I can set allocatemem to 1000000000 on my machine that allocates over 950 MB
science_man_88 is offline   Reply With Quote
Old 2015-09-05, 13:41   #9
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

164268 Posts
Default

Quote:
Originally Posted by Batalov View Post
You didn't even consider that they are one and the same?
Note also that numbers of the form k*2^n +/- c is the ENTIRE SET OF ODD INTEGERS!!!!!


Numbers of the form x^n +/-1 are special. (cyclotomy!!!!)

Why on Earth people think k* 2^n + c is special is beyond me.
R.D. Silverman is offline   Reply With Quote
Old 2015-09-05, 14:45   #10
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

26·131 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
Why on Earth people think k* 2^n + c is special is beyond me.
maybe because they care for other potential groupings around a number like sexy primes or cousin primes ?

Last fiddled with by science_man_88 on 2015-09-05 at 14:46
science_man_88 is offline   Reply With Quote
Old 2015-09-05, 15:09   #11
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(3,3^1118781+1)/3

5×1,811 Posts
Default

Quote:
Originally Posted by T.Rex View Post
Ha ha ha ! No ! ;) I should have considered... but too busy with other stuff.
Now, he has succeeded to use you as a sock puppet.
Think about it. If he wanted to post it himself, under three different names (and on ten other boards, just like inimitable Don Blazys), he would have! And he had already done that.
Now he used you to post this tripe once again.

Don't you feel used?
Batalov is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Compositeness test jnml Miscellaneous Math 10 2018-01-27 16: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
Conjectured Primality Test for 2^p-1, (2^p+1)/3 and (2^2^n+1) T.Rex Math 75 2007-09-04 07:53
PRP => LL-tests? Holmes Math 1 2005-05-13 17:18

All times are UTC. The time now is 13:19.

Sat Jul 4 13:19:55 UTC 2020 up 101 days, 10:52, 2 users, load averages: 1.88, 1.86, 1.76

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