mersenneforum.org

mersenneforum.org (https://www.mersenneforum.org/index.php)
-   Miscellaneous Math (https://www.mersenneforum.org/forumdisplay.php?f=56)
-   -   Conjectured compositeness tests for N=k⋅2n±c by Predrag (https://www.mersenneforum.org/showthread.php?t=20467)

T.Rex 2015-09-04 21:23

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 [URL="http://math.stackexchange.com/questions/1394160/conjectured-compositeness-tests-for-n-k-cdot-2n-pm-c"]a question in StackExchange[/URL] 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 [TEX]N=k2^n \pm c[/TEX], c odd for sure, with simple but powerful definitions using the LLT ([TEX]S_n \equiv S_{n-1}^2-2 ~ \pmod{N}[/TEX]) but also higher LLT functions (Chebichev) for the seed and for the last term of the sequence, after [TEX]n-1[/TEX] 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)))[/CODE]

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


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. [TEX]P_2(x) = x^2-2[/TEX]

[TEX]\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[/TEX]

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

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

T.Rex 2015-09-04 21:33

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

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=T.Rex;409609][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)))[/CODE][/QUOTE]

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)))[/CODE]

T.Rex 2015-09-05 10:26

[QUOTE=Batalov;409612]You didn't even consider that they are one and the same?[/QUOTE]
Ha ha ha ! No ! ;) I should have considered... but too busy with other stuff.

T.Rex 2015-09-05 10:30

[QUOTE=science_man_88;409618]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); ... ) }
[/CODE][/QUOTE]
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=T.Rex;409642]I do not think that this will speed up the computation, since PARI goes in Stack overflow quickly. Modulo helps to keep s small.[/QUOTE]

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=T.Rex;409642]I do not think that this will speed up the computation, since PARI goes in Stack overflow quickly. Modulo helps to keep s small.[/QUOTE]

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=Batalov;409612]You didn't even consider that they are one and the same?[/QUOTE]

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=R.D. Silverman;409659]Why on Earth people think k* 2^n + c is special is beyond me.[/QUOTE]

maybe because they care for other potential groupings around a number like sexy primes or cousin primes ?

Batalov 2015-09-05 15:09

[QUOTE=T.Rex;409641]Ha ha ha ! No ! ;) I should have considered... but too busy with other stuff.[/QUOTE]
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?


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

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.