Score:3

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

gb flag

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.

Score:3
pe flag

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.

gb flag
Could you please elaborate more on how you reached (p-1)/d using Lagrange’s theorem? Thanks
gb flag
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.
pe flag
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.
pe flag
Edited things to make more sense.
kelalaka avatar
in flag
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$
pe flag
If $B$ is missing a factor $d$ of $p-1$, then $a^B \bmod p$ is equivalent to $a^{(p-1)/d \cdot \dots} \bmod p$. So what we're counting is the number of elements such that $a^{(p-1)/d} = 1 \bmod p$, i.e., the number of elements of order (at most) $(p-1)/d$.
kelalaka avatar
in flag
I think _having a number $d$ corresponding to the missing factors_ confuses me. I read it like there are $d$ factors missing. Now I can see better that $d \nmid B$ is not the size of the set $\{d\mid d \nmid B \}$.
kelalaka avatar
in flag
Let $d$ be the product of factors of $p−1$ that $B$ does not contain... This is true if $d$ is prime, however, then $d$ is not a prime the product misses some number like let $2$ and $3$ is missing, however, the product $d = 6$ doesn't involve $2,4,9,$,etc. Don't we need the inclusion-exclusion there?
pe flag
I don't understand your point. For any element, $a^{p-1} = 1$. If $B$ is missing 2 and 3, i.e., $d=6$, then what you are computing instead (ignoring the non-divisors of $p-1$ in $B$) is $a^{(p-1)/6}$, because every other divisor of $p-1$ is already in there. So the method will work for elements such that $a^{(p-1)/6} = 1$. Note that $d$ and $p-1$ can share factors, for example you could have $p-1 = 2^5 3^3 5^4$ and $d = 10$, which would imply $B = 2^4 3^3 5^3 \cdot \dots$, in which case the method would work when $a^{2^4 3^3 5^3} = a^{(p-1)/10} = 1$.
mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.