galois.pollard_p1

galois.pollard_p1(n: int, B: int, B2: int | None = None) → int

Attempts to find a non-trivial factor of $n$ if it has a prime factor $p$ such that $p - 1$ is $B$ -smooth.

Parameters:¶

n: int¶: An odd composite integer $n > 2$ that is not a prime power.
B: int¶: The smoothness bound $B > 2$ .
B2: int | None = None¶: The smoothness bound $B_{2}$ for the optional second step of the algorithm. The default is None which will not perform the second step.

Returns:¶

A non-trivial factor of $n$ .

Raises:¶

RuntimeError – If a non-trivial factor cannot be found.

See also

factors, pollard_rho

Notes

For a given odd composite $n$ with a prime factor $p$ , Pollard’s $p - 1$ algorithm can discover a non-trivial factor of $n$ if $p - 1$ is $B$ -smooth. Specifically, the prime factorization must satisfy $p - 1 = p_{1}^{e_{1}} \dots p_{k}^{e_{k}}$ with each $p_{i} \leq B$ .

A extension of Pollard’s $p - 1$ algorithm allows a prime factor $p$ to be $B$ -smooth with the exception of one prime factor $B < p_{k + 1} \leq B_{2}$ . In this case, the prime factorization is $p - 1 = p_{1}^{e_{1}} \dots p_{k}^{e_{k}} p_{k + 1}$ . Often $B_{2}$ is chosen such that $B_{2} ≫ B$ .

References

Section 3.2.3 from https://cacr.uwaterloo.ca/hac/about/chap3.pdf

Examples

Here, $n = p q$ where $p - 1$ is 1039-smooth and $q - 1$ is 17-smooth.

In [1]: p, q = 1458757, 1326001

In [2]: galois.factors(p - 1)
Out[2]: ([2, 3, 13, 1039], [2, 3, 1, 1])

In [3]: galois.factors(q - 1)
Out[3]: ([2, 3, 5, 13, 17], [4, 1, 3, 1, 1])

Searching with $B = 15$ will not recover a prime factor.

In [4]: galois.pollard_p1(p*q, 15)
---------------------------------------------------------------------------
RuntimeError                              Traceback (most recent call last)
Cell In[4], line 1
----> 1 galois.pollard_p1(p*q, 15)

File /opt/hostedtoolcache/Python/3.8.16/x64/lib/python3.8/site-packages/galois/_prime.py:1177, in pollard_p1(n, B, B2)
   1174     if d not in [1, n]:
   1175         return d
-> 1177 raise RuntimeError(
   1178     f"A non-trivial factor of {n} could not be found using the Pollard p-1 algorithm "
   1179     f"with smoothness bound {B} and secondary bound {B2}."
   1180 )

RuntimeError: A non-trivial factor of 1934313240757 could not be found using the Pollard p-1 algorithm with smoothness bound 15 and secondary bound None.

Searching with $B = 17$ will recover the prime factor $q$ .

In [5]: galois.pollard_p1(p*q, 17)
Out[5]: 1326001

Searching $B = 15$ will not recover a prime factor in the first step, but will find $q$ in the second step because $p_{k + 1} = 17$ satisfies $15 < 17 \leq 100$ .

In [6]: galois.pollard_p1(p*q, 15, B2=100)
Out[6]: 1326001

Pollard’s $p - 1$ algorithm may return a composite factor.

In [7]: n = 2133861346249

In [8]: galois.factors(n)
Out[8]: ([37, 41, 5471, 257107], [1, 1, 1, 1])

In [9]: galois.pollard_p1(n, 10)
Out[9]: 1517

In [10]: 37*41
Out[10]: 1517