Conjectured compositeness tests for N=k⋅2n±c by Predrag

T.Rex · 2015-09-04, 21:23

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}$

T.Rex · 2015-09-04, 21:33

Thanks to primus to have warned me about Predrag's publication in StackExchange.

Batalov · 2015-09-04, 22:09

You didn't even consider that they are one and the same?

science_man_88 · 2015-09-05, 01:28

Quote:

Originally Posted by T.Rex

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)))

T.Rex · 2015-09-05, 10:26

Quote:

Originally Posted by Batalov

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 · 2015-09-05, 10:30

Quote:

Originally Posted by science_man_88

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.

axn · 2015-09-05, 12:23

Quote:

Originally Posted by T.Rex

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.

science_man_88 · 2015-09-05, 13:40

Quote:

Originally Posted by T.Rex

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

R.D. Silverman · 2015-09-05, 13:41

Quote:

Originally Posted by Batalov

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.

science_man_88 · 2015-09-05, 14:45

Quote:

Originally Posted by R.D. Silverman

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 ?

Batalov · 2015-09-05, 15:09

Quote:

Originally Posted by T.Rex

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?

2015-09-04, 21:23	#1
T.Rex Feb 2004 France 3²×103 Posts	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=2c+1,g, N=k2^n+sc; 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(2polchebyshev(k,1,a/2),N); sn=Mod((-1)^d2polchebyshev(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,2c+1,1000))) for(k=1,100,for(c=0,50,CEk2c(k,-(2c+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*

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

2015-09-04, 21:33	#2
T.Rex Feb 2004 France 3²·103 Posts	Thanks to primus to have warned me about Predrag's publication in StackExchange.

2015-09-04, 22:09	#3
Batalov "Serge" Mar 2008 Phi(4,2^7658614+1)/2 2²×3³×7×13 Posts	You didn't even consider that they are one and the same?