1from titan_pylib.math.is_prime64 import is_prime64
2from collections import Counter
3from math import gcd
4from random import Random
5
6
[docs]
7class PollardRho:
8
9 # 高速素因数分解
10 # 124376107291
11
12 _rand = Random(None)
13 _L = [2, 325, 9375, 28178, 450775, 9780504, 1795265022]
14 _P200 = [
15 2,
16 3,
17 5,
18 7,
19 11,
20 13,
21 17,
22 19,
23 23,
24 29,
25 31,
26 37,
27 41,
28 43,
29 47,
30 53,
31 59,
32 61,
33 67,
34 71,
35 73,
36 79,
37 83,
38 89,
39 97,
40 101,
41 103,
42 107,
43 109,
44 113,
45 127,
46 131,
47 137,
48 139,
49 149,
50 151,
51 157,
52 163,
53 167,
54 173,
55 179,
56 181,
57 191,
58 193,
59 197,
60 199,
61 ]
62
[docs]
63 @classmethod
64 def factorization(cls, n: int) -> Counter:
65 res = Counter()
66 for p in cls._P200:
67 if n % p == 0:
68 cnt = 0
69 while n % p == 0:
70 cnt += 1
71 n //= p
72 res[p] = cnt
73 if n == 1:
74 return res
75 while n > 1:
76 f = cls._pollard_rho(n)
77 cnt = 0
78 while n % f == 0:
79 cnt += 1
80 n //= f
81 res[f] += cnt
82 return res
83
84 @classmethod
85 def _pollard_rho(cls, n: int) -> int:
86 if is_prime64(n):
87 return n
88 while True:
89 x = cls._rand.randrange(n)
90 c = cls._rand.randrange(n)
91 y = (x * x + c) % n
92 d = 1
93 while d == 1:
94 d = gcd(x - y, n)
95 x = (x * x + c) % n
96 y = (y * y + c) % n
97 y = (y * y + c) % n
98 if 1 < d < n:
99 return cls._pollard_rho(d)