# galois.pollard_p1¶

galois.pollard_p1(n, B, B2=None)

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

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$$.

Parameters
• n (int) – An odd composite integer $$n > 2$$ that is not a prime power.

• B (int) – The smoothness bound $$B > 2$$.

• B2 (int, optional) – 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.

Return type

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)


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