# Why is the pollard's (p-1)-Method not efficient for some numbers?

I have an algorithm for the method, where the idea is to choose a random number $$a$$, and then a bound $$B$$. Then we find $$k=\prod_{\substack{p\in\mathbb{P}\\ p^{e}\leq B}}p^e$$ and calculate $$\gcd(a^k-1,n)$$. And if this is not $$1$$ or $$n$$ (the number to be factorized), then we found a divisor. For some numbers this method won't work, for example for $$n=132193=163\cdot 811$$. But I don't have a concrete explanation why the method doesn't work for that number. I thought it might have to do with the fact that in this case, $$p-1$$ would be:
$$162=2\cdot 3^4$$
or $$810=2\cdot 3^4 \cdot 5$$
in both cases I get a small prime number ($$3$$) but with a large exponent, so I think that might difficult the selection of the bound $$B$$, but I don't know exactly how or why...
Could someone help me clarify this doubt? Thank you

• In what sense does the method not work for that $n$? If you happen to pick $a = 17$ (which is a cube modulo $163$ but not modulo $811$) and $27 \leqslant B < 81$, then you get the factor $163$. Jan 29, 2020 at 20:31
• Well, that is exactly what I'm trying to find out. I guess the choice of $a$ you made is one of the very few that work Jan 29, 2020 at 20:38
• Few, but probably not very few. Yes, it was deliberately chosen to work. So you want to know why the method works (comparatively) badly for that $n$ (and a number of others)? Jan 29, 2020 at 20:43
• Yes, exactly. In the problem formulation it says that for this specific number one would "need much luck" to factorize $132193$ with the pollard p-1 method... Jan 29, 2020 at 21:10
• Unless one knows the factorisation, then one can easily find parameters $a$ and $B$ for which the method will succeed. I need to look up how $B$ is picked in the algorithm, that influences how much luck one would need. Jan 29, 2020 at 21:14

The reason why Pollard's $$p-1$$-method doesn't work well for $$n = 163\cdot 811$$ is that the largest prime power dividing $$163-1$$ is the same as the largest prime power that divides $$811-1$$. Thus in this example $$p-1$$ and $$q-1$$ both become $$B$$-powersmooth for the same $$B$$.
Generally, the idea of the algorithm is that a prime factor $$p$$ of $$n$$ will divide $$a^k - 1$$ (where $$a$$ is coprime to $$n$$) if $$k$$ is a multiple of $$p-1$$, but usually a prime factor $$q$$ of $$n$$ will not divide it if $$k$$ is not a multiple of $$q-1$$. Of course for some $$a$$, $$q$$ will nevertheless divide $$a^k - 1$$, but for that to happen $$a$$ must be a $$\frac{q-1}{\gcd(k,q-1)}$$-th power residue modulo $$q$$, and there aren't too many such.
Since the exponent $$k$$ is defined as the product of all prime powers $$\leqslant B$$, all prime factors $$p$$ of $$n$$ for which $$p-1$$ is $$B$$-powersmooth will divide $$a^k - 1$$ for all $$a$$ coprime to $$n$$, and the prime factors $$q$$ of $$n$$ for which $$q-1$$ is not $$B$$-powersmooth will only rarely divide $$a^k-1$$.
Thus when for a squarefree $$n = p_1\cdot \ldots \cdot p_r$$ all the $$p_{\rho}-1$$ have the same largest prime power divisor $$q^m$$, the algorithm can only find a nontrivial divisor of $$n$$ when $$B < q^m$$, and the chosen base $$a$$ is a suitable power residue modulo some but not all of the $$p_{\rho}$$. (If $$n$$ is not squarefree, then for a prime $$p$$ with $$p^2 \mid n$$ it's likely that $$p \mid a^k - 1$$ but $$p^2 \nmid a^k-1$$ for $$B \geqslant q^m$$, so we'd get a nontrivial factor with high[ish] probability even if $$q^m$$ is the maximal prime power divisor of all $$p_{\rho}-1$$.)
If the largest prime power dividing $$p_{\rho}-1$$ is not the same for all $$\rho$$, then a value of $$B$$ between the smallest and the largest of these maximal prime power divisors will find a factor with high probability.
If one executes the algorithm with a fixed $$a$$ and increments $$B$$ (starting with $$B \geqslant 5$$, say) for $$n = 163\cdot 811$$, one needs a bit of luck to choose an $$a$$ that is a cubic (or ninth power, or $$27^{\text{th}}$$ power) residue modulo one of the factors but not the other. One can reduce the amount of luck needed by using several $$a$$ for each $$B$$. This of course multiplies the work by the number of bases one tries. A strategy that avoids that multiplication is to execute the algorithm with a fixed base $$a$$, and when $$\gcd(a^k-1,n) = n$$ for $$k = k(B)$$ but $$\gcd(a^k-1,n) = 1$$ for $$k = k(B-1)$$, then it's likely that $$B$$ is the largest prime power dividing each of the $$p_{\rho}-1$$, say $$B = q^m$$, and trying several other bases for $$k(B-1) = k(B)/q$$ has decent chances to find a factor. Since the probability that a randomly chosen number is a $$q^{\text{th}}$$ power residue modulo a prime $$p \equiv 1 \pmod{q}$$ is roughly $$1/q$$, if being a $$q^{\text{th}}$$ power residue modulo different such primes is independent, the probability of finding a base that is a $$q^{\text{th}}$$ power residue modulo one of two prime factors is about $$\frac{2q-1}{q^2}$$. Then we would expect to find a factor within about $$q$$ tries. If $$q$$ is large, that's bad, but for small $$q$$ it's feasible. (Of course there's still luck needed, but we have a guesstimate how much luck we need. However, if our guess that $$B$$ was the largest prime power divisor of all the $$p_{\rho}$$ was wrong, our guesstimate may be quite wrong too.)