galois.pollard_p1(n: int, B: int, B2: = 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: = 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.

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/latest/lib/python3.8/site-packages/galois/_prime.py:1181, in pollard_p1(n, B, B2)
1178     if d not in [1, n]:
1179         return d
-> 1181 raise RuntimeError(
1182     f"A non-trivial factor of {n} could not be found using the Pollard p-1 algorithm "
1183     f"with smoothness bound {B} and secondary bound {B2}."
1184 )

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