# Probability of choosing a base successfully in Pollard p-1 factorization method

In a problem about pollard p-1 factorization method, where $$n=pq$$. We choose some random base $$a$$ , and an exponent $$B$$, where hopefully $$p-1$$ has small prime factors, and if so we hope to estimate $$p = \gcd(a^B-1,n)$$.

We wish to estimate the probability that for a given exponent $$B$$, a randomly chosen base $$a$$ satisfies that $$p$$ divides $$a^B-1$$ and $$q$$ doesn‘t divide $$a^B-1$$. We assume that the prime factorizations of $$p-1,q-1,\text{ and } B$$ are known. How can I estimate the probability of success? Thank you.

The $$p-1$$ method works, by definition, whenever the multiplicative order of $$a$$ modulo $$p$$ is a divisor of $$B$$. If $$B$$ is a multiple of $$p-1$$, that is, the maximum possible multiplicative order of $$a$$, the probability is $$1$$.

We are concerned, then, with the case where $$B$$ does not contain every divisor of $$p-1$$. If it contains none of them, the probability is $$0$$.

The key challenge here is, having a number $$d$$ corresponding to the factors of of $$p-1$$ missing from $$B$$, to count the number of elements of $$\mathbb{F}_p^{\ast}$$ whose order is $$(p-1)/d$$ or any of its divisors. Those elements are precisely the ones for which those missing factors from their order do not affect the success of the factorization. If $$d=1$$, the number of elements is $$p-1$$, that is, the whole range. If $$d = 2$$, this number is the number of elements such that $$a^{(p-1)/2} = 1$$, that is, the number of quadratic residues modulo $$p$$ (excluding 0), which happens to be $$(p-1)/2$$.

More generally, since $$\mathbb{F}_p^{\ast}$$ is cyclic every element can be represented as $$g^e$$, for some primitive element $$g$$ and an exponent $$e$$. Our goal is to count the number of solutions $$e$$ to $$g^{e(p-1)/d} = 1 \pmod{p}\,,$$ or in other words $$e(p-1)/d = 0 \pmod{p-1}\,,$$ which we can see is the number of multiples of $$d$$ up to $$p-1$$, i.e., $$\frac{p-1}{d}$$.

Let $$d$$ be product of factors of $$p-1$$ that $$B$$ does not contain, i.e., $$d = \frac{p-1}{\gcd(p-1, B)}$$. Then the probability of the order of a randomly selected $$a$$ splitting $$n$$ is given by $$\frac{(p-1)/d}{p-1} = \frac{1}{d}\,.$$

For example, suppose $$p = 15554690395797258751$$. Now suppose $$B$$ contains all the factors of $$p-1 = 2\cdot 3 \cdot 5^4 \cdot 11 \cdot 1021 \cdot 25013 \cdot 14765423$$ except $$2$$. Then the probability that $$p-1$$ factorization works is $$1/2$$. If $$B$$ on the other hand is too low and doesn't include $$14765423$$, which is the more likely case, the factorization probability becomes $$1/14765423$$.

For $$q-1$$ the same considerations apply. However, when considering both $$p-1$$ and $$q-1$$ at the same time, one needs to subtract the case where both succeed, in which case there is also no factorization. Like above, suppose $$d_1$$ are the missing $$p-1$$ factors from $$B$$, and $$d_2$$ the ones from $$q-1$$. Then we have a probability of success $$\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}\,,$$ that is, $$p-1$$ succeeds and $$q-1$$ fails, or $$q-1$$ succeeds and $$p-1$$ fails.

• Could you please elaborate more on how you reached (p-1)/d using Lagrange’s theorem? Thanks Commented Jan 7, 2022 at 19:17
• For example, if we take p=19 and d =6, then we have ord(1)=1, ord(2,3,10,19,14,15)=18, ord(4,5,6,9,16,17)=9, ord(7,11)=3, ord(8,12)=6, ord(18)=2. Thus, the number of elements whose order does not divide d is 12 which is not equal to (p-1)/d. Commented Jan 7, 2022 at 20:30
• In your example we have $p-1 = 2\cdot 3^2$ and we are missing from $B$ $d = 6 = 2\cdot 3$. But this means that $B = 3\cdot \dots$, since we are only missing one of the powers of $3$. So what we need for success is that the order of $a$ not be a multiple of $2$ and $3^{2}$, of which there are $3 = 18/6$ elements, $\{1,7,11\}$. My explanation above is clearly incomplete, since it only holds for primes without powers, but I believe the result itself is correct. I'll see what I can do. Commented Jan 7, 2022 at 21:51
• Edited things to make more sense. Commented Jan 7, 2022 at 23:44
• I'm confused about the third paragraph, which is the relation between $d$ the number of missing factors of $B$ and $(p-1)/d$. Why the number of the missing factors have order $(p-1)/d$ Commented Jan 10, 2022 at 19:51