## Puzzle: Counterexample for a 1+1+2 Selfridge prime test

Expand Messages
• Dear David, i checked the following test with a list of Pseudoprimes
Message 1 of 7 , Mar 9, 2014
Dear David,

i checked the following test with a list of Pseudoprimes < 10^16 and did not found a counterexample

David, please, can you look for one counterexample, if there exists one.

the test has an easy structure and has the following conditions :

1. p should not be a square and  p=3 mod 4 and p=1 mod 6
2. choose a with jac (a, p)=-1 and check a^[(p-1)/2]=-1 mod p
if this test fails p is definitly not a prime, this is a p-1 test.
3. try to find a 3. root of 1 by making a similar Rabbin-Miller test with exponent 3 instead of 2
( a^[(p-1)/3]=x mod p and x <>1)
The chance to find a 3. root is 2/3, perhaps there is a more sophisticated way to calculate
this.
if  x=1 repeat step 2. and 3 . which can be combined so that the costs are only one selfridge
4. Calculate in the complex field (x^2+x*i)^[(p+1)/2]=-1 or = 1 mod p resp.
(x^2+x*i)^[(p+1)/4]= a+bi mod p where a=0
The norm of |x^2+x*i|=(x^2+x*i)(x^2-x*i) =
x^4+x^2 =           with x^3=1
x + x^2 = -1 mod p  with  x^2+x+1 = 0 mod p
is -1 mod p
This is a p+1 test with a reduction to a base with norm= -1, where p+1 is not divisible by 3
and which cost 2 selfridges.

Paul mentionned that this test would cost 1+1+2 Selfridges
which is too much for a probablistic test as i know.

This test should be a candidate for me to give a sufficient test
and should be stronger than my test before
because the norm of (x^2+x*i)=-1 instead of the test before with norm = 1

Besides : all primes with p=3 mod 4 and p=1 mod 6 and < 10^9 passes the test,
where the point 1., 2., 3. is easy to prove, but for the point 4.  i am looking for an explication.

David, it would be nice from you, if you give me a gentle mathematic response,
perhaps with some explication, why the test could fail.

I wish you a peaceful evening and a good start in the week,
primes are beautiful flowers in the universe and
i appreciate really a fair mathematical discussion in order to learn a little bit more.

Thanks in advance from the primes to the gremlins
Bernhard
• ... Hence p = 7 mod 12. ... Hence x^2+x+1 = 0 mod p. ... False for primes! The result is +/- i mod p. My gremlins cannot solve badly stated problems. David
Message 2 of 7 , Mar 9, 2014
Bernhard Helmes wrote:

> p=3 mod 4 and p=1 mod 6

Hence p = 7 mod 12.

> a^[(p-1)/2]= -1 mod p
> a^[(p-1)/3] = x mod p and x <> 1

Hence x^2+x+1 = 0 mod p.

> (x^2+x*i)^[(p+1)/2] = -1 or = 1 mod p

False for primes! The result is +/- i mod p.

My gremlins cannot solve badly stated problems.

David
• Proposed primality test: 1) p = 7 mod 12 is not a square, 2) kronecker(a,p) = - 1, 3) a^((p-1)/2) = -1 mod p, 4) gcd(x-1,p) = 1, where x = a^((p-1)/3), 5)
Message 3 of 7 , Mar 10, 2014
Proposed primality test:

1) p = 7 mod 12 is not a square,
2) kronecker(a,p) = - 1,
3) a^((p-1)/2) = -1 mod p,
4) gcd(x-1,p) = 1, where x = a^((p-1)/3),
5) (x^2+i*x)^(p+1) = -1 mod p.

It's quite easy to find pseudoprimes.

{tst(p, a, x) =
p%12 == 7 && !issquare(p) &&
kronecker(a,p) == -1 &&
Mod(a,p)^((p-1)/2) == -1 &&
gcd(x-1,p) == 1 && Mod(a,p)^((p-1)/3) == x &&
(Mod(x,p)*(x+I))^(p+1) == -1;}

{if(tst(271*8161, 7260, 682620), print("Fooled"));}

Fooled

David
• Dear David, i thank you for your work and successful search for the counterexample. Does it make any difference if the test is limited to p = 3 mod 8 in
Message 4 of 7 , Mar 12, 2014
Dear David,

i thank you for your work and successful search for the counterexample.
Does it make any difference if the test is limited to p = 3 mod 8 in addition ?

> Proposed primality test:

> 1) p = 7 mod 12 is not a square,
> 2) kronecker(a,p) = - 1,
> 3) a^((p-1)/2) = -1 mod p,
> 4) gcd(x-1,p) = 1, where x = a^((p-1)/3),
5) (x^2+i*x)^[(p+1)/2] = i, -i mod p.

The best greetings to the gremlins
Bernhard
• Bernhard Helmes asked: . Does it make any difference if the test is limited to p = 3 mod 8 in addition ? No. Here is a counterexample with composite p = 19
Message 5 of 7 , Mar 12, 2014

.> Does it make any difference if the test is limited to p = 3 mod 8 in addition ?

No. Here is a counterexample with composite p = 19 mod 24.

{p=
675961081605237787645326669827132867421964707102288445595128\
306767364368922625365751637387079135941412241725625718182659\
797220975595414553817336272156315877518713459900369575786759\
069060577760998993405179409380771964650863026553544931148603\
852397726534883765167569700179809784567165598901315490849439\
643483131;}

{a=
143183781681819085621274459662205664353066281708044561938474\
561078078825094915532720327449936152812575165723359597491154\
987675822372398122684609431293757111072607893728179485857573\
561016496252852435832824395580172292440970359198725505460012\
729132839536797444771147293062929495356986071030574294827961\
789589258;}

{test(p,a)=local(m,x,r,t);
if(p%24==19&&!issquare(p)&&kronecker(a,p)==-1,
m=Mod(a,p)^((p-1)/6);x=m^2;
if(m^3==-1&&gcd(lift(x)-1,p)==1,r=(x^2+I*x)^((p+1)/2);
if(r==I||r==-I,t=1)));t;}

{if(test(p,a)&&!isprime(p),
print(" Fooled at "#Str(p)" digits"));}

Fooled at 309 digits

Challenge for Paul Underwood: how did I choose a ?
Challenge for Kermit Rose: can you factorize p ?
Clue for both: p = 1 mod 137.

David (per proxy the 300 digit gremlins)

• I can not say exactly how you chose a . In general terms, you used your usual trickery -- which I should have studied more than I did -- and CRT, which is
Message 6 of 7 , Mar 12, 2014
I can not say exactly how you chose "a". In general terms, you used your usual trickery -- which I should have studied more than I did -- and CRT, which is guaranteed to work with any such test that has at most one lucas component.

However, I am still mindlessly testing my double lucas tests and the 2-selfridge test. The latter has reached 7*10^13 and 10^15 is in the pipeline,

Paul
• ... In the past you were more shrewd and sought for an exponent k such that a^k-1 is not coprime to p. This should work again. However (if I did not err) you
Message 7 of 7 , Mar 12, 2014
Paul Underwood wrote:

> I can not say exactly how you chose "a".

In the past you were more shrewd and sought for
an exponent k such that a^k-1  is not coprime to p.

This should work again. However (if I did not err)
you will not be able to use that result, directly, to factorize
the semiprime p, as was possible in many previous cases.

Factorization of p should be within the scope of Kermit,
whose has been training his code on previous semiprimes,
albeit at less than 300 digits.

> guaranteed to work with any such test that has at most one lucas component.

Yes, provided that there is a free parameter (in this case, a) to adjust.
I wish Bernhard would accept this and stop asking to be stomped
on by my gremlins, who by now regard him as a very soft target.