The $p-1$ metoda funcționează, prin definiție, ori de câte ori ordine multiplicativă de $a$ modulo $p$ este un divizor al $B$. Dacă $B$ este un multiplu al $p-1$, adică ordinul multiplicativ maxim posibil al $a$, probabilitatea este $1$.
Ne preocupă, deci, cazul în care $B$ face nu conţin fiecare divizor al $p-1$. Dacă nu conține niciuna dintre ele, probabilitatea este $0$.
Provocarea cheie aici este să ai un număr $d$ corespunzătoare factorilor de a $p-1$ lipsă din $B$, pentru a număra numărul de elemente ale $\mathbb{F}_p^{\ast}$ a cărui ordine este $(p-1)/d$ sau oricare dintre divizorii săi. Acele elemente sunt tocmai cele pentru care acei factori lipsă din ordinea lor nu afectează succesul factorizării.
Dacă $d=1$, numărul de elemente este $p-1$, adică toată gama. Dacă $d = 2$, acest număr este numărul de elemente astfel încât $a^{(p-1)/2} = 1$, adică numărul de reziduuri pătratice modulo $p$ (excluzând 0), care se întâmplă să fie $(p-1)/2$.
Mai general, din moment ce $\mathbb{F}_p^{\ast}$ este ciclic fiecare element poate fi reprezentat ca $g^e$, pentru unii element primitiv $g$ și un exponent $e$. Scopul nostru este să numărăm numărul de soluții $e$ la
$$
g^{e(p-1)/d} = 1 \pmod{p}\,,
$$
sau cu alte cuvinte
$$
e(p-1)/d = 0 \pmod{p-1}\,,
$$
care putem vedea este numărul de multipli ai $d$ pâna la $p-1$, adică $\frac{p-1}{d}$.
Lăsa $d$ fi produs de factori ai $p-1$ acea $B$ nu conține, adică $d = \frac{p-1}{\gcd(p-1, B)}$. Apoi probabilitatea de ordine a unui selectat aleatoriu $a$ despicare $n$ este dat de
$$
\frac{(p-1)/d}{p-1} = \frac{1}{d}\,.
$$
De exemplu, să presupunem $p = 15554690395797258751$. Acum să presupunem $B$ conţine toţi factorii de $p-1 = 2\cdot 3 \cdot 5^4 \cdot 11 \cdot 1021 \cdot 25013 \cdot 14765423$ cu exceptia $2$. Apoi probabilitatea ca $p-1$ lucrările de factorizare este $1/2$. Dacă $B$ pe de altă parte este prea scăzut și nu include $14765423$, care este cazul mai probabil, probabilitatea de factorizare devine $1/14765423$.
Pentru $q-1$ se aplică aceleași considerații. Cu toate acestea, când le luăm în considerare pe ambele $p-1$ și $q-1$ în același timp, trebuie să scădem cazul în care ambele reușesc, caz în care nu există nici factorizare. Ca mai sus, să presupunem $d_1$ sunt cei dispăruți $p-1$ factori din $B$, și $d_2$ cele de la $q-1$. Atunci avem o probabilitate de succes
$$
\frac{1}{d_1}\left(1 - \frac{1}{d_2}\right) + \frac{1}{d_2}\left(1 - \frac{1}{d_1}\right) = \frac{1}{d_1} + \frac{1}{d_2} - \frac{2}{d_1d_2}\,,
$$
acesta este, $p-1$ reușește și $q-1$ eșuează, sau $q-1$ reușește și $p-1$ eșuează.
