3
$\begingroup$

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.

$\endgroup$

1 Answer 1

3
$\begingroup$

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.

$\endgroup$
9
  • $\begingroup$ Could you please elaborate more on how you reached (p-1)/d using Lagrange’s theorem? Thanks $\endgroup$
    – CryptoN00b
    Commented Jan 7, 2022 at 19:17
  • $\begingroup$ 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. $\endgroup$
    – CryptoN00b
    Commented Jan 7, 2022 at 20:30
  • $\begingroup$ 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. $\endgroup$ Commented Jan 7, 2022 at 21:51
  • $\begingroup$ Edited things to make more sense. $\endgroup$ Commented Jan 7, 2022 at 23:44
  • $\begingroup$ 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$ $\endgroup$
    – kelalaka
    Commented Jan 10, 2022 at 19:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.