.
Liczbę która nie spełnia warunków powyższego twierdzenia nazywa się świadkiem złożoności liczby
Twierdzenie 2 Jeśli jest nieparzystą liczbą złożoną, to w zbiorze jest co najwyżej liczb niebędących świadkami jej złożoności.
Przykład Należy określić, czy liczba jest pierwsza.
Zapisując w postaci otrzymuje się oraz Następnie trzeba wybrać losowo liczbę Jeśli wylosowaną liczbą jest wtedy dla ze zbioru i więc nierównoważne
Ponieważ to albo liczba 221 jest pierwsza, albo 174 jest fałszywym świadkiem dla 221. W tym przypadku następuje losowanie kolejnej wartość tym razem i więc nierównoważne
A zatem 137 jest świadkiem złożoności 221, a 174 jest faktycznie fałszywym świadkiem. W tym przypadku test pozwala także dokonać rozkładu liczby: NWD(137−1, 221) = 17 221 / 17 = 13 zatem 221 = 17 · 13
Dokładność testu i wersje deterministyczne Można pokazać, że dla dowolnej złożonej nieparzystej liczby naturalnej co najmniej 3/4 możliwych wartości jest dobrymi świadkami złożoności tej liczby. Jeśli zatem przeprowadzamy losowych prób, prawdopodobieństwo, że określimy liczbę złożoną jako pierwszą wynosi co najwyżej