- --- In primenumbers@yahoogroups.com,

"djbroadhurst" <david.broadhurst@...> wrote:

> {p=3281;x=1062;y=1600;

The gremlins now have more than 23,000 pseudoprimes

> if(kronecker(3,p)==-1&&

> Mod(3,p)^((p-1)/2)==-1&&

> x^2-3*y^2==Mod(1,p)&&

> Mod(Mod(1,p)*(x+y*A),A^2-3)^p==x-y*A&&

> !isprime(p),print(" fooled"));}

>

> fooled

that fool Bernhard's test. But before revealing them,

they await a response to the very simple case, above.

David - Dear David,

the amount of counterexamples sounds impressively.

I suppose that there are a lot of p=1 mod 4.

I think that i will publish soon a test which separates between p=1 mod 4 and p=3 mod 4,

but i would like to check first some list by myself in order to save some time for you and to get

some more informations.

How does it feel to be a "keeper" of such a lot of interesting gremlins :-)

A new and better proposition:

A. Let p an element of N with p=3 mod 4,

m the greatest power of 2 with 2^m*r=p+1

and 2^m < r

1. choose a prime a with jacobi (a, p)=-1

2. Verify a^(p-1)/2=-1 mod p

3. Depending on the a choose the pell solution of x, y with

x^2-ay^2=1 mod p

http://mathworld.wolfram.com/PellEquation.html

4. Verify that (x+yA)^(2^m)<>1 mod p with A=sqrt (a)

because gcd (p-1, p+1) = 2

5. Calculate and verify (x+yA)^p=x-yA mod p

6. Calculate (x+yA)^r=x(r)+y(r)A mod p and

verify that gcd (y(r), p)=1

(The point 6. derives of a factorisation test, is cheap and powerful

because gcd (y(n), p) > 1 results gcd (y(m), p) > 1 with m=n*t)

if 1.-6. is ok. then p is a prime.

David, you will realize that i abstain form the choose of the smallest a

and that i add the point 4. for good reasons

I wish you a peaceful and pleasant weekend

Bernhard - Bernhard Helmes wrote:

> A new and better proposition

The gremlins refuse to consider a

test that is not true for primes.

Consider, for example, the prime

p = 1037*2^8-1 = 265471

and set a = 3, x = 2, y = 1.

Then this prime fails your latest wriggle:

> (x+yA)^(2^m)<>1 mod p with A=sqrt(a)

print(Mod(Mod(1,265471)*(2+A),A^2-3)^(2^8));

Mod(Mod(1, 265471), A^2 - 3)

Please do not post probable primality "tests"

that are failed by primes.

David (trying to control the grumpy gremlins:-) A peaceful day for all group members,

dear David,

I changed only the point 3.

Is this changement a sharper condition or is this mathematically seen the same ?

I. For p=3 mod 41. choose the smallest prime a with jacobi (a, p)=-1

2. Verify a^(p-1)/2=-1 mod p

[This is the p-1 test which proves that a is a non quadric residuum]

3. Depending on the a choose the pell solution of x, y with

x^2-ay^2=-1 mod p (the minus is the change :-)

4. Calculate and verify (x+yA)^p=x-yA mod p with A=sqrt (a)

5. m the greatest power of 2 with 2^m*r=p+1 and 2^m < rCalculate (x+yA)^r=x(r)+y(r)A mod p and

verify that gcd (y(r), p)=1

[This is a strong p+1 test with a solution of the according pell equation]

if 1. - 5. is true then p should be a prime

I think that this "wriggle" will include that there exist a cycle group with order t > 2 and t | r

There is no need to hurry up for the gremlins,

the prime numbers will exist a little longer. ;-)

Friendly greetings from the primes

Bernhard