$p-1$ метод работает, по определению, всякий раз, когда мультипликативный порядок из $а$ по модулю $р$ является делителем $В$. Если $В$ является кратным $p-1$, то есть максимально возможный мультипликативный порядок $а$, вероятность $1$.
Итак, нас интересует случай, когда $В$ делает нет содержать каждый делитель $p-1$. Если он не содержит ни одного из них, вероятность равна $0$.
Ключевая проблема здесь заключается в том, чтобы иметь число $д$ соответствующие факторам $p-1$ отсутствует в $В$, чтобы подсчитать количество элементов $\mathbb{F}_p^{\ast}$ чей порядок $(p-1)/д$ или любой из его делителей. Это именно те элементы, для которых недостающие множители из их порядка не влияют на успех факторизации.
Если $д=1$, количество элементов $p-1$, то есть весь диапазон. Если $д = 2$, это число есть количество таких элементов, что $а^{(р-1)/2} = 1$, то есть количество квадратичные вычеты по модулю $р$ (исключая 0), что оказывается $(p-1)/2$.
В более общем плане, поскольку $\mathbb{F}_p^{\ast}$ является циклическим каждый элемент может быть представлен как $г^е$, для некоторых примитивный элемент $г$ и показатель степени $е$. Наша цель — подсчитать количество решений $е$ к
$$
g^{e(p-1)/d} = 1 \pmod{p}\,,
$$
или другими словами
$$
e(p-1)/d = 0 \pmod{p-1}\,,
$$
которое мы можем видеть, является числом, кратным $д$ вплоть до $p-1$, т. е. $\frac{p-1}{d}$.
Позволять $д$ быть произведением факторов $p-1$ что $В$ не содержит, т. е. $d = \frac{p-1}{\gcd(p-1, B)}$. Тогда вероятность порядка случайно выбранного $а$ расщепление $n$ дан кем-то
$$
\frac{(p-1)/d}{p-1} = \frac{1}{d}\,.
$$
Например, предположим $р = 15554690395797258751$. Теперь предположим $В$ содержит все факторы $p-1 = 2\cdot 3 \cdot 5^4 \cdot 11 \cdot 1021 \cdot 25013 \cdot 14765423$ кроме $2$. Тогда вероятность того, что $p-1$ факторизация работает $1/2$. Если $В$ с другой стороны, слишком низкий и не включает $14765423$, что более вероятно, вероятность факторизации становится $1/14765423$.
За $q-1$ применяются те же соображения. Однако при рассмотрении обоих $p-1$ и $q-1$ в то же время нужно вычесть случай, когда оба успешны, и в этом случае также нет факторизации. Как и выше, предположим $d_1$ пропавшие без вести $p-1$ факторы от $В$, и $d_2$ те из $q-1$. Тогда у нас есть вероятность успеха
$$
\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}\,,
$$
это, $p-1$ преуспевает и $q-1$ терпит неудачу или $q-1$ преуспевает и $p-1$ терпит неудачу.
