W każdym innym przypadku jest liczbą złożoną.

Opis algorytmu wymagał uzupełniania o dwa elementy: dowód poprawności oraz ustalenie jego złożoności obliczeniowej. Zostało to zrealizowane przez pokazanie, że odpowiednie zawsze można znaleźć, ustalenie wielkości tego i udowodnienie, że testy przeprowadzone w drugiej części są wystarczające do stwierdzenia pierwszości

Ponieważ czas działania obu części zależy od wielkości podanie górnego ograniczenia na wystarczyło do określenia złożoności algorytmu na . To górne ograniczenie jest bardzo zgrubne – jeśli prawdziwe jest założenie o rozkładzie liczb pierwszych Sophie Germain, to złożoność algorytmu automatycznie maleje do

Bibliografia Manindra Agrawal, Neeraj Kayal, Nitin Saxena, „PRIMES is in P”, Annals of Mathematics 160 (2004), no. 2, s. 781–793.

AKS