Search
Pohlig-Hellman
Last updated
Oct 23, 2022
Edit Source
# 説明
中国剰余定理を用いて大きな群を複数の小さな群の直積に分割する。
# 実装
1
2
3
4
5
6
7
8
9
| fact = factor(G.order())
ord = int(G.order())
dlogs = []
for p, e in fact:
t = ord // p ^ e
dlog = discrete_log(t * Q, t * G, operation="+")
dlogs += [dlog]
print(crt(dlogs, primes))
|
# 使用例
# 参考