Fatto cruciale 1: Se q è primo i passi 1-5 dell'algoritmo di Rabin ritornano sempre "probabilmente primo"
Fatto cruciale 2: Se q è composto i passi 1-5 dell'algoritmo di Rabin ritornano "probabilmente primo" per al più 1/4 delle possibili scelte di a. Non lo dimostriamo (ma non è difficile).
Con k iterazioni la probabilità di errore diventa al più (1/4)k (questa è una stima prudente; per la maggior parte dei q la probabilità è molto più bassa).