## sufficient test for primes with certificate

Expand Messages
• 1. A criteria to distinguish primes from composite numbers: a) If and only if an odd number p 5 has two solutions in the field of adjoined square root A with
Message 1 of 33 , May 7, 2012
1. A criteria to distinguish primes from composite numbers:

a) If and only if an odd number p > 5 has two solutions
in the field of adjoined square root A
with A quadratic residuum and element of N
where the solutions consist the form f+g*sqrt (A) with f=0 and g=/=0
for the equation x^2 = 1 mod p
then p is a prime.

(For the primes 2, 3, 5 there does not exist a suitable A)

b) An odd number which is composite does not have any solution
in the field of adjoined square root A
with A a quadratic residuum and element of N
where the solution should consist
of the form f+g*sqrt (A) with f=0 and g=/=0
for the equation x^2= 1 mod p

i made an implementation of the algorithm:

http://109.90.3.58/devalco/sufficient_test_for_primes_with_certificate.html

the old version can be find under:
http://109.90.3.58/devalco/sufficient_test_for_primes_with_certificat.html

Description of the new algorithm:

1. I make a strong probablistic test:
http://primes.utm.edu/prove/prove2_3.html

2. I make a similiar rabin-miller test for (1+sqrt(A))^[(p-1)]/2^r
if p is prime there is a chance of 50% for one test to find a certificate
with [g*sqrt (A)]^2=1 using the first criteria for primes where x^2=1

If p is not prime then one test with (1+sqrt(A))^(p-1)=/=1
will prove that p is not prime.

2. mathematical proof by Kermit Rose

Let p be prime.

Let A be a square residue mod p.
Then there exist an integer x mod p such that x^2 = A mod p.

Does there exist
(f + g sqrt(A)) such that (f + g sqrt(A))^2 = 1 mod p and g is not equal
to zero mod p.

(f = g sqrt(A))^2 = ( f^2 + A g^2) + (2 f g) sqrt(A) = 1

2 f g = 0 mod p

Since g is not zero mod p,
and 2 f g = 0 mod p, and p is prime, it must be that

f = 0 mod p.

(g sqrt(A) )^2 = A g^2 = 1

has exactly the two solutions

g = 1/x and g = -1/x, where x^2 = A mod p.

Now, let P be composite = p1^k1 * p2^k2 * ....

Let A be a square residue mod P.
Then A is a square residue mod p1, p2, ...

let x1^2 = A mod p1,
x2^2 = A mod p2,
etc

(f + g sqrt(A))^2 = (f^2 + A g^2) + (2 f g) sqrt(A) = 1 mod P.

2 f g = 0 mod P.

Since P is composite, there exist non-zero values of f which satisfy 2 f
g = 0 mod P.

Let g be a divisor of P.
since P is odd, g is odd, and P/g is odd.

set f = (P + P/g)/2

Then 2 f g = 2 [ (P + P/g)/2] [g] = [P + P/g][g] = gP + P = 0 mod P

f^2 + A g^2 = [ (P + P/g)/2]^2 + A g^2 = (P/g)^2 + A g^2 mod P

Since A is a square residue mod P, there exist x such that x^2 = A mod P.

(P/g)^2 + (x g)^2 = 1 mod P, where g divides P.

(xg)^2 = 1 - (P/g)^2.

That is, we will find counter example if we can find a composite
such that
1 - (P/g)^2 is a square residue mod P, where g is a divisor of P.
• ... I compiled a better version of my code with gmp 5.0.5, on a different box running at 3.6GHz and got some better timings { 17.505s pfgw (3-prp) 1m1.986s
Message 33 of 33 , Sep 21, 2012
--- In primenumbers@yahoogroups.com, "paulunderwooduk" <paulunderwood@...> wrote:
:

> I ran various "minimal \lambda+2" tests on Gilbert Mozzo's 20,000 digit PRP, 5890*10^19996+2^66422-3 (x=1), using a 2.4GHz core:
> {
> 0m32.374s pfgw64 (3-prp)
> 1m9.876s pfgw64 -t
> 1m53.535s pfgw64 -tp
> 3m0.483s pfgw64 -tc
> 5m12.972s pfgw64 scriptify
> 4m4.811s gmp (-O3/no pgo)
> 4m9.148 pari-gp
> 1m15s theoretical Woltman implementation
> }
>

I compiled a better version of my code with gmp 5.0.5, on a different box running at 3.6GHz and got some better timings
{
17.505s pfgw (3-prp)
1m1.986s pfgw -tp
1m13.789s gmp (-O3/no pgo)
}

Paul
Your message has been successfully submitted and would be delivered to recipients shortly.