sufficent proof for primes

Expand Messages
• A beautifull evening, I tried to find another sufficent proof for primes especially of the form p:=x^2+x+1. I found a test similar to Pocklington which runs as
Message 1 of 1 , Apr 21, 2006
A beautifull evening,

I tried to find another sufficent proof for primes especially of the
form p:=x^2+x+1. I found a test similar to Pocklington which runs as
follow:

p:=x^2+x+1, the factorisation of x+1 with x+1:=f1*f2*...*fn is known.
I choose a base b which has jacobi (b, fi)=-1
calculate erg_0:=b^x mod p and
erg_1:=erg_0^f1 mod p, gcd (erg_1, erg_0)=1 is checked and
erg_2:=erg_1^f2 mod p, gcd (erg_2, erg_1)=1 is checked until
erg_n:=erg_n-1^fn mod p must be equal 1 and gcd (erg_n, erg_n-1)=1 is
checked.

I suppose that that is a sufficent proof for p because all roots of fi
exist. But it might be that i am not sure.

The test needs the same conditions as the test from pocklington and i
think it is as fast as the test from pocklington.

Please send me a note, if i have reinvent the wheel.
Please let me know if the test is right or not.

Best regards from the primes
Bernhard

x:=2;
while TRUE do
p:=x^2+x+1;
f:=ifactor (x+1);
base:=3;

while TRUE do
change_base:=FALSE;
for i from 1 to (nops (f))/2 do
if numlib::jacobi (f[2*i], base)=1 then
change_base:=TRUE;
break;
end_if;
end_for;
if change_base=FALSE then
break;
else
base:=nextprime (base+1);
end_if
end_while;

erg:=powermod (base, x, p);

prim:=TRUE;
for i from 1 to (nops (f))/2 do
for j from 1 to f[2*i+1] do
res:=powermod (erg, f[2*i], p);
if res=erg or gcd (res, erg)>1 then
prim:=FALSE;
break;
end_if;
erg:=res;
end_for;
end_for;
if prim=TRUE and erg=1 then
print ("Prim", p, f);
if isprime (p)=FALSE then
print ("Falsch", ifactor (p));
return ();
end_if;
end_if;
x:=x+1;
end_while;

I checked all p up to 5733048401263 and did not find any
counterexample.
Your message has been successfully submitted and would be delivered to recipients shortly.