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\), if found. None if not found.

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 \le 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} \le 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 \gg B\).

References

Examples

Here, \(n = pq\) 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 ~/checkouts/readthedocs.org/user_builds/galois/envs/v0.3.1/lib/python3.8/site-packages/galois/_prime.py:1195, in pollard_p1(n, B, B2)
   1192     if d not in [1, n]:
   1193         return d
-> 1195 raise RuntimeError(
   1196     f"A non-trivial factor of {n} could not be found using the Pollard p-1 algorithm "
   1197     f"with smoothness bound {B} and secondary bound {B2}."
   1198 )

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 \le 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