-
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:¶
- Returns:¶
A non-trivial factor of \(n\).
- Raises:¶
RuntimeError – If a non-trivial factor cannot be found.
See also
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) Cell In[4], line 1 ----> 1 galois.pollard_p1(p*q, 15) File /opt/hostedtoolcache/Python/3.11.10/x64/lib/python3.11/site-packages/galois/_prime.py:1182, in pollard_p1(n, B, B2) 1179 if d not in [1, n]: 1180 return d -> 1182 raise RuntimeError( 1183 f"A non-trivial factor of {n} could not be found using the Pollard p-1 algorithm " 1184 f"with smoothness bound {B} and secondary bound {B2}." 1185 ) 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