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

David (licensed gremlin tamer)