Inhaltsverzeichnis

Development of
Algorithmic Constructions


This is a fast test for primes mod 4 = 3.
It is sufficent for all primes mod 4 = 3 below 10^11.

let be b the smallest non quadric residium.
Necessary: b^((p-1)/2)=p-1 mod p
Sufficent: (b+I)^p = b^p + I^p = b - I


                                   10, 2

                                  100, 13

                                 1000, 87

                                10000, 619

                               100000, 4808

                              1000000, 39322

Concerning the primes mod 4 = 1 the condition

b^((p-1)/2)=p-1 mod p
(b+I)^p = b^p + I^p = b + I
is not sufficent.

The first counterexamples for p < 1000000 are :

29341 = 13*37*61, base = 2
314821 = 13*61*397, base = 2
410041 = 41*73*137, base = 13
721801 = 601*1201, base = 7