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 = 1 mod 4

Algorithm

Implementation in Mupad

mathematical proof

This is a sufficent test for primes p = 1 mod 4 and not for primes p = 3 mod 4.
The test uses the arithmetic in the ring natural numbers with an adjoined square root mod p.
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 (1+A)^p=1-A mod p with A=sqrt (a)
    If (1+A)^p=/=1-A mod p then p is definitively not a prime

Implementation in Mupad



                                   10, 1

                                  100, 11

                                 1000, 80

                                10000, 609

                               100000, 4783

                              1000000, 39175

                             10000000, 332180

                            100000000, 2880504

                           1000000000, 25423491

mathematical proof