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
- $\begingroup$ 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$. $\endgroup$Daniel Fischer– Daniel Fischer2020-01-29 20:31:06 +00:00Commented Jan 29, 2020 at 20:31
- $\begingroup$ 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 $\endgroup$M-S-R– M-S-R2020-01-29 20:38:21 +00:00Commented Jan 29, 2020 at 20:38
- $\begingroup$ 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)? $\endgroup$Daniel Fischer– Daniel Fischer2020-01-29 20:43:49 +00:00Commented Jan 29, 2020 at 20:43
- $\begingroup$ 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... $\endgroup$M-S-R– M-S-R2020-01-29 21:10:07 +00:00Commented Jan 29, 2020 at 21:10
- $\begingroup$ 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. $\endgroup$Daniel Fischer– Daniel Fischer2020-01-29 21:14:05 +00:00Commented Jan 29, 2020 at 21:14
1 Answer
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.)