Các $p-1$ phương pháp hoạt động, theo định nghĩa, bất cứ khi nào thứ tự nhân của $a$ modulo $p$ là một ước số của $B$. Nếu $B$ là bội số của $p-1$, nghĩa là, thứ tự nhân tối đa có thể có của $a$, xác suất là $1$.
Do đó, chúng tôi quan tâm đến trường hợp $B$ làm không phải chứa mọi ước của $p-1$. Nếu nó không chứa cái nào trong số chúng, thì xác suất là $0$.
Thách thức chính ở đây là, có một số $d$ tương ứng với các yếu tố của $p-1$ mất tích từ $B$, để đếm số phần tử của $\mathbb{F}_p^{\ast}$ thứ tự của ai $(p-1)/d$ hoặc bất kỳ ước số nào của nó. Những yếu tố đó chính xác là những yếu tố mà những yếu tố bị thiếu trong thứ tự của chúng không ảnh hưởng đến sự thành công của phép nhân.
Nếu $d=1$, số phần tử là $p-1$, nghĩa là, toàn bộ phạm vi. Nếu $d = 2$, số này là số phần tử sao cho $a^{(p-1)/2} = 1$, tức là số dư lượng bậc hai modulo $p$ (không bao gồm 0), xảy ra là $(p-1)/2$.
Tổng quát hơn, kể từ khi $\mathbb{F}_p^{\ast}$ là tuần hoàn mọi phần tử có thể được biểu diễn dưới dạng $g^e$, đối với một số yếu tố nguyên thủy $g$ và một số mũ $e$. Mục tiêu của chúng tôi là đếm số lượng giải pháp $e$ đến
$$
g^{e(p-1)/d} = 1 \pmod{p}\,,
$$
hay nói cách khác
$$
e(p-1)/d = 0 \pmod{p-1}\,,
$$
mà chúng ta có thể thấy là số bội số của $d$ lên đến $p-1$, I E., $\frac{p-1}{d}$.
Để cho $d$ là sản phẩm của các yếu tố của $p-1$ điều đó $B$ không chứa, tức là, $d = \frac{p-1}{\gcd(p-1, B)}$. Sau đó, xác suất thứ tự của một lựa chọn ngẫu nhiên $a$ tách $n$ được đưa ra bởi
$$
\frac{(p-1)/d}{p-1} = \frac{1}{d}\,.
$$
Ví dụ, giả sử $p = 15554690395797258751$. Bây giờ giả sử $B$ chứa tất cả các yếu tố của $p-1 = 2\cdot 3 \cdot 5^4 \cdot 11 \cdot 1021 \cdot 25013 \cdot 14765423$ ngoại trừ $2$. Khi đó xác suất mà $p-1$ công việc phân tích thừa số là $1/2$. Nếu $B$ mặt khác là quá thấp và không bao gồm $14765423$, đó là trường hợp có nhiều khả năng xảy ra hơn, xác suất nhân tố hóa trở thành $1/14765423$.
Vì $q-1$ những cân nhắc tương tự được áp dụng. Tuy nhiên, khi xem xét cả hai $p-1$ và $q-1$ đồng thời, người ta cần loại trừ trường hợp cả hai đều thành công, trong trường hợp đó cũng không có phân tích thành thừa số. Như trên, giả sử $d_1$ là người mất tích $p-1$ yếu tố từ $B$, và $d_2$ những cái từ $q-1$. Sau đó, chúng tôi có một xác suất thành công
$$
\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}\,,
$$
đó là, $p-1$ thành công và $q-1$ thất bại, hoặc $q-1$ thành công và $p-1$ thất bại.
