离散对数笔记

发表于 本文字数： 1.8k 阅读时长 ≈ 2 分钟
有关离散对数的简要笔记

离散对数

基本问题

离散对数基本问题是解决形如 \[ a^y\equiv x\pmod{p} \] 求解 \(y\) 的值，我们记作 \[ y=\log_a{x}\pmod{p} \] 显然我们会想到朴素的爆破算法，计算每一个 \(x+kp\) 对 \(a\) 的对数，如果结果是整数，那么这个值恰好是 \(y\)。

同时需要知道，当 \(p\) 不为质数时，结果可能不唯一。

小步大步法（baby-step-giant-step）

原理

小步大步法的优势是可以指定一个范围，同时算法内部迭代速度是线性的，算法复杂度是 \(\sqrt{p}\)。

代码

一般使用 Sagemath 自带的算法，需要指定一个范围。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
from sage.groups.generic import bsgs

p = getPrime(128)
Fp = GF(p)
a = Fp(getPrime(32))
y = Fp(getPrime(32))
b = a ^ y
print(f'{p = }')
print(f'{a = }')
print(f'{y = }')
print(f'{b = }')
"""
p = 308246233383857285750026618406218229381
a = 2189570113
y = 2989311631
b = 157894317370901577057351162302392667811
"""

result = bsgs(mod(a, p), mod(b, p), bounds=(2**31, 2**32))
print(f'{result = }')
"""
result = 2989311631
"""

Pohlig-Hellman 算法

原理

在 \(GF(p)\) 的阶（order）为光滑数时，易分解为较小的域，此时在小域内求解离散对数速度会快得多。

特别地，当 \(p\) 为素数时，\(p-1\) 一般都为光滑数。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
p = 6897108443075981744484758716081045417854227543713106404294789655180105457499042179717447342593790180943415014044830872925165163457476209819356694244840079
b = 1315637864146686255246675143589215932218700984880749264689270214639479160648747323586062096067740047809798944996253169402675772469028914904598116394230426
a = 6789891305297779556556571922812978922375073901749764215969003309869718878076269545304055843125301553103531252334876560433405451108895206969904268456786139

n = p - 1
primes = list(filter(lambda x: x < 2 ** 32, (base ** exp for base, exp in factor(n))))
dlogs = []
for fac in primes:
    t = int(n) // int(fac)
    dlog = discrete_log(pow(b, t, p), pow(a, t, p))
    dlogs.append(dlog)
yp = int(crt(dlogs, primes))
print(yp)

此时需要注意，如果 \(y_p\neq y\)，即 \(y=y_p+kp\)，那么可能需要小范围爆破：

1
2
3
4
for i in range(2**10):
    res = long_to_bytes(k + i * prod(primes))
    if res.startswith(b'flag'):
        print(res)