mersenneforum.org Conjectured compositeness tests for N=k⋅2n±c by Predrag
 Register FAQ Search Today's Posts Mark Forums Read

 2015-09-04, 21:23 #1 T.Rex     Feb 2004 France 911 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=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
 2015-09-04, 21:33 #2 T.Rex     Feb 2004 France 911 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(3,3^1118781+1)/3 5·1,811 Posts You didn't even consider that they are one and the same?
2015-09-05, 01:28   #4
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

26×131 Posts

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

2015-09-05, 10:26   #5
T.Rex

Feb 2004
France

911 Posts

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.

2015-09-05, 10:30   #6
T.Rex

Feb 2004
France

911 Posts

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.

2015-09-05, 12:23   #7
axn

Jun 2003

11×421 Posts

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.

2015-09-05, 13:40   #8
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

100000110000002 Posts

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

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

Nov 2003

164268 Posts

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.

2015-09-05, 14:45   #10
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

26·131 Posts

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 ?

Last fiddled with by science_man_88 on 2015-09-05 at 14:46

2015-09-05, 15:09   #11
Batalov

"Serge"
Mar 2008
Phi(3,3^1118781+1)/3

5×1,811 Posts

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?

 Similar Threads Thread Thread Starter Forum Replies Last Post jnml Miscellaneous Math 10 2018-01-27 16:20 primus Miscellaneous Math 1 2014-10-12 09:25 primus Computer Science & Computational Number Theory 16 2014-08-15 01:15 T.Rex Math 75 2007-09-04 07:53 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

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.