Inhaltsverzeichnis

Development of
Algorithmic Constructions

Germany

sufficient test for primes with certificate

Status:

1. search for counterexamples: done
2. mathematical proof: not yet
3. speed : 4 (=1+3) Selfridges
4. Use for p = 3 mod 4

Algorithm

Implementation in Mupad

mathematical proof

This is a sufficent test for primes p = 3 mod 4 and not for primes p = 1 mod 4.
The test uses the arithmetic in the complex field.
No factorisation of p-1 or p+1 is needed.
One Fermat test and one test in the adjoined square root field is needed.
4 (=1+3) Selfridges are needed for proving that a number is a prime.
This test is faster than the AKS, but slower than the Baillie-PSW, which is unproved.

Algorithm:

1. Check if p is not a square, otherwise you will not find an a for 2.

2. a is a number with jacobi (a,p)=-1

3. Calculate if a^((p-1)/2) = -1 mod p ,
    if this test is wrong, p is not a prime

4. Calculate (a+I)^p=a-I mod p
    If (a+I)^p=/=a-I mod p then p is definitively not a prime

Implementation in Mupad



                                   10, 2

                                  100, 13

                                 1000, 87

                                10000, 619

                               100000, 4808

                              1000000, 39322

                             10000000, 332398

                            100000000, 2880950

                           1000000000, 25424042

mathematical proof