1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
| def recover_prime_from_xor(n, x):
bits = n.bit_length()
candidates = [0] # possible low bits of p
for i in range(bits):
mask = (1 << (i+1)) - 1
a_low = x & mask
n_low = n & mask
new = []
for p_low in candidates:
for b in (0, 1):
p_try = p_low | (b << i)
q_try = p_try ^ a_low
if (p_try * q_try) & mask == n_low:
new.append(p_try)
if not new:
raise ValueError(f"no fit at bit {i}")
candidates = new # 保持所有可能，通常数量很小
# 尝试哪些候选是真正的质因子
for p in candidates:
if p and n % p == 0:
return p
q = p ^ x
if q and n % q == 0:
return n // q
raise ValueError("no factor found")
|
