2. <tex> a^{2^r*d} </tex> $mod n &ne; -1$, pentru $0 &le; r &le; s-1$
Daca ambele relatii sunt simultan indeplinite pentru un numar $a$, atunci stim ca numarul $Nr$ este compus. Daca cel putin una dintre conditii nu este indeplinita se continua verificarile pentru un alt numar $a$. Numerele $a$ cu care se vor face verificarile pot fi, de exemplu, primele 6 numere prime sau o multime de numere prime alese aleator (mai mult de $3$, dar nu mai mult de $7$, pentru ca solutia sa se incadreze in timp).

Complexitatea logaritmica a algoritmului provine de la faptul ca ridicarile la putere se vor efectua in $O(log n)$

h2. 'Kcity':problema/kcity