Niestety powyższy algorytm można oszukać, tak żeby zaakceptował liczbę złożoną. W tym celu można podać mu fałszywy rozkład na czynniki pierwsze n −1, w którym będą znajdowały się liczby złożone. Przykładowo załóżmy, że twierdzimy, że 85 jest pierwsza, podając świadka x= 4 i równanie 84=6×14 jako rozkład n −1. Wtedy:
4 jest względnie pierwsze z 85 485−1 ≡ 1 (mod 85) 4(85−1)/6 ≡ 16 (mod 85), 4(85−1)/14 ≡ 16 (mod 85)
Algorytm wywnioskuje, że 85 jest pierwsza. Zauważmy, że nie możemy samodzielnie szukać rozkładu n −1 na czynniki pierwsze, ponieważ nie znamy algorytmu, który robi to w wielomianowym czasie.
Lepszym sposobem rozwiązania tego problemu jest udostępnienie certyfikatów pierwszości również dla każdego czynnika n −1: w tej samej postaci, ale mniejszych i łatwiejszych do sprawdzenia. Postępujemy w ten sposób rekurencyjnie, aż dojdziemy do czynników o których wiemy, że są pierwsze (np. do 2). Kompletny certyfikat ma wtedy postać drzewa ze znanymi liczbami pierwszymi w liściach.