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\), 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

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

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)
<ipython-input-4-01f0edd40f44> in <module>
----> 1 galois.pollard_p1(p*q, 15)

~/repos/galois/galois/_prime.py in pollard_p1(n, B, B2)
   1169             return d
   1170 
-> 1171     raise RuntimeError(f"A non-trivial factor of {n} could not be found using the Pollard p-1 algorithm with smoothness bound {B} and secondary bound {B2}.")
   1172 
   1173 

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