# Development ofAlgorithmic Constructions

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

### 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

• // Fast binary exponentation for complex numbers
powermod_I:=proc (zahl, exp, modul)
begin
bit:=exp mod 2;
if bit = 1 then
res:=zahl;
exp:=(exp-1)/2
else
res:=1;
exp:=exp/2;
end_if;

while TRUE do
bit:=exp mod 2;
res_re:=Re (res_quadrat) mod modul;
res_im:=Im (res_quadrat) mod modul;
if bit = 0 then
else
res_re:=Re (res) mod modul;
res_im:=Im (res) mod modul;
res:=res_re+res_im*I;
end_if;
exp:=(exp-bit)/2;
if exp=0 then
// return (1) if zahl=a-I
if (res_re=Re (zahl) and res_im=modul-1) then
return (1);
end_if;
return (0);
end_if;
end_while;
end;

anz:=2;
grenze:=10;

for p from 11 to 1000000003 step 4 do
// Ausgabe
if p>grenze then
print (grenze, anz);
grenze:=grenze*10;
end_if;

// 1. exclude the squares because there is no jacobi (a, n^2)=-1
w:=isqrt (p);
if w^2=p then
else
//  2. jacobi (base, p)=-1
base:=2;
while TRUE do
if numlib::jacobi (base, p)=-1 then
break;
end_if;
base:=base+1;
end_while;

// 3. base^[(p-1)/2]=-1 mod p
res:=powermod (base, (p-1)/2, p);
if res=p-1 then
// 4. (a+I)^p=a-I mod p
if (powermod_I (base+I, p, p)=1) then
anz:=anz+1;
end_if;
end_if;
end_if;
end_for;
```

10, 2

100, 13

1000, 87

10000, 619

100000, 4808

1000000, 39322

10000000, 332398

100000000, 2880950

1000000000, 25424042

```