皮蛋厂的学习日记系列为山东警察学院网安社成员日常学习分享，希望能与大家共同学习、共同进步~

• 0x0前言

• 0x1 baby step giant step算法

• 0x2 Pohlig-Hellman算法

• 0x3 Pollard’s rho算法

• 𝐁𝐢𝐫𝐭𝐡𝐝𝐚𝐲 𝐓𝐫𝐢𝐜𝐤

• 0x4 Pollard's p-1 算法

• 0x5 Williams's p + 1 算法

• 0x6 其他算法

0x0前言

在去打美赛之前，碰到好多离散对数问题，这部分并没有好好学过，利用准备黄河流域网络安全技能邀请赛的公差整理一下，代码全都来自互联网

0x1 baby step giant step算法

即大步小步算法，算法目的是让a^x=b(mod p)的求解速度更快一点   通常要求gcd(a,p)==1

该算法就是将方程中的x写成x = np - q的形式，其中p就是大步giant step，而q就是小步baby step。

上述方程可以写为：

把a^-q移动到等式右边，就变成了：

def babystep_giantstep(g, y, p):
    m = int((p-1)**0.5 + 0.5)
    # Baby step
    table = {}
    gr = 1  # g^r
    for r in range(m):
        table[gr] = r
        gr = (gr * g) % p
    # Giant step
    gm = pow(g, -m, p)  
    ygqm = y            
    for q in range(m):
        if ygqm in table: 
            return q * m + table[ygqm]
        ygqm = (ygqm * gm) % p
    return None
g = 
y = 
p = 
x = babystep_giantstep(g, y, p)
print(x)
print(pow(g, x, p) == y)

0x2 Pohlig-Hellman算法

是一种求解光滑阶循环群上的离散对数的方法，要求p-1一定是光滑的，否则复杂度依然很高

记a^x = b(mod p)的原根为g

则a=g^a_i ,b = a=g^b_i 原根的次幂可以在[1,p-1]中一一对应，因此a_i 和 b_i 是一定存在的

即g^a_ix = g^b_i (mod p)

所以a_ix = b_i(mod p-1)

之后步骤如下：

1、将φ(p)=p-1的质因子分解，即

2、对于每一个质因子p_i，可以列出方程

3、令r=1，求(a^x)^(p-1)/p_ir=(b)^(p-1)/p_ir(mod p)

4、展开x，将剩下的代入得

5、从第二项开始。后边的每一项都是1（因为欧拉定理），因此我们可以得到式子：

6、得到a₀后，令r=r+1，回到步骤3，最终可以得到：

7、在算出m个关于x的式子之后，可以用CRT来梭

# Baby-step Giant-step法
def babystep_giantstep(g, y, p, q=None):
    if q is None:
        q = p - 1
    m = int(q**0.5 + 0.5)
    # Baby step
    table = {}
    gr = 1  # g^r
    for r in range(m):
        table[gr] = r
        gr = (gr * g) % p
    # Giant step
    try:
        gm = pow(g, -m, p)  # gm = g^{-m}
    except:
        return None
    ygqm = y                # ygqm = y * g^{-qm}
    for q in range(m):
        if ygqm in table:
            return q * m + table[ygqm]
        ygqm = (ygqm * gm) % p
    return None
# Pohlig–Hellman法
def pohlig_hellman_DLP(g, y, p):
    crt_moduli = []
    crt_remain = []
    for q, _ in factor(p-1):
        x = babystep_giantstep(pow(g,(p-1)//q,p), pow(y,(p-1)//q,p), p, q)
        if (x is None) or (x <= 1):
            continue
        crt_moduli.append(q)
        crt_remain.append(x)
    x = crt(crt_remain, crt_moduli)
    return x
g = 
y = 
p = 
x = pohlig_hellman_DLP(g, y, p)
print(x)
print(pow(g, x, p) == y)

0x3 Pollard’s rho算法

在描述这个算法之前，先要引入一个小tricks

𝐁𝐢𝐫𝐭𝐡𝐝𝐚𝐲 𝐓𝐫𝐢𝐜𝐤

pq为素数，N=pq

我们随机从[1,N]中选择一个数，这个数是pq的可能性几乎为零，所以我们需要重复运行算法来提高概率。那么我们现在可以提出一个不同的问题：

不再只选取一个整数，而是选取k个数，那是否存在xi-xj能够整除N

当，时，这个可能性就会提高到50%

❝

在区间[𝟐, 𝑵 − 𝟏]中随即选取 𝒌 个数，𝒙𝟏, … … , 𝒙𝒌 判断是否存在𝒈𝒄𝒅(𝒙𝒊 − 𝒙𝒚 , 𝑵) > 𝟏, 若存在，𝒈𝒄𝒅(𝒙𝒊 − 𝒙𝒚 ,𝑵) 是𝑵的一个因子 ( 𝒑 或 𝒒 )

回到Pollard’s rho算法之中

n为离散对数的阶，设n的最大素因子是p，假定存在两个整数，x和x' ∈ Z_n，使得x≠x'且x=x'( mod p)，那么有p≤gcd(x-x' , n) < n

所以我们可以通过计算最大公因子得到n的一个非平凡因子，并且事先并不需要知道p的值

由于并不知道p的值，可以先随机选择一个子集X ⊂ Z_n ,然后对所有不同的x，x' ∈ X，判断gcd(x-x',n)是否为1。这个方法要成功需要映射x→x (mod p)在X中至少存在一个碰撞。根据𝐁𝐢𝐫𝐭𝐡𝐝𝐚𝐲 𝐓𝐫𝐢𝐜𝐤可以进行分析：如果∣ X ∣ ≈ 1.71 时，至少存在一个碰撞的概率是50%。

该算法大大减少了求gcd的次数，子集X并不是随机产生的，而是事先确定一个整系数多项式f，并取x₁ ∈ Z_n ,令：

这就产生了集合X={x1,x2,······，xm}。

运算的核心思想如下：

❝

如果x_i = x_j (mod p)，由于f是整系数多项式，所以f(xi) = f(xj) (mod p)。又因为p|n，所以

同理有x_j+1 mod p = f(x_j) mod p。因此x_i+1=x_j+1 mod p。

进一步有：如果x_i = x_j(mod p)，则对∀δ ≥ 0，有x_i+δ = x_j+δ (mod p)。

记l = j-i，可知x_i' = x_=' (mod p) 如果j'≥i’≥i且 j‘ - i’ ≡ 0 (mod 1 )。

这样将x₁、x₂、x₃、x₄、x₅、x₆、x₇等连接起来，就可以作图：

def pollard_rho(g, y, p):
    q = (p-1) // 2
    def new_xab(x, a, b,  g, y, p, q):
        subset = x % 3
        if subset == 0:
            return ((x*x) % p, (a*2) % q, (b*2) % q)
        if subset == 1:
            return ((x*g) % p, (a+1) % q, b        )
        if subset == 2:
            return ((x*y) % p, a        , (b+1) % q)
    x, a, b = 1, 0, 0
    X, A, B = x, a, b
    for i in range(1, p):
        x, a, b = new_xab(x, a, b,  g, y, p, q)
        X, A, B = new_xab(X, A, B,  g, y, p, q)
        X, A, B = new_xab(X, A, B,  g, y, p, q)
        if x == X:
            break
    res = ((a - A) * pow(B - b, -1, q)) % q
    if pow(g, res, p) == y:
        return res
    if pow(g, res + q, p) == y:
        return res + q
    return None
g = 
y = 
p = 
x = pollard_rho(g, y, p)
print(x)
print(pow(g, x, p) == y)

0x4 Pollard's p-1 算法

如果一个整数的所有素因子都不大于B，那我们称这个整数是B-smooth数

如果一个整数的所有素因子的对应指数次幂不大于B，我们称这个整数是B-powersmooth数

算法核心：

为了分解合数n。设数n的一个因子是p，若p-1的每个因子q满足≤B（B是界），此时必有：(p-1)|B!

证明过程：

❝

设：

显然上式成立

Pollard's p-1 算法是直接计算a=2^B!(mod n)和gcd(a-1, n)，这个最大公因子就是n的一个非平凡因子。

证明过程：

❝

由于p|n，所以有

又根据Fermat定理，

因为2^(p-1)|2^B!，所以

即p|(a − 1) 。于是p就是a − 1和n的公因子。最大公因子当然是其中一个。

代码如下：

def pollard_p_1(n,B):
    """
    Factor n = p*q (p is B-smooth)
    :param n:
    :param B:
    :return: d = p
    """
    # step 1
    a = 2
    # step 2
    false_range = int(0.8*B)
    for j in range(2,false_range):
    # We assume n had a factor > 0.8B,so we can do less gcd
        a = pow(a, j, n)
    d = 0
    for j in range(false_range,B+1):
    # step 3
        a = pow(a, j, n)
    # step 4
        d = gcd(a-1, n)
    # step 5
        if 1<d<n:
            return d

0x5 Williams's p + 1 算法

比较少见，我也不太明白，只能先记录下来

https://ctf-wiki.org/crypto/asymmetric/rsa/rsa_module_attack/#p-1_1

def mlucas(v, a, n):
    """ Helper function for williams_pp1().  Multiplies along a Lucas sequence modulo n. """
    v1, v2 = v, (v**2 - 2) % n
    for bit in bin(a)[3:]: v1, v2 = ((v1**2 - 2) % n, (v1*v2 - v) % n) if bit == "0" else ((v1*v2 - v) % n, (v2**2 - 2) % n)
    return v1
for v in count(1):
    for p in primegen():
        e = ilog(isqrt(n), p)
        if e == 0: break
        for _ in xrange(e): v = mlucas(v, p, n)
        g = gcd(v-2, n)
        if 1 < g < n: return g # g|n
        if g == n: break

0x6 其他算法

当然还有很多其他的甚至都没有听说过的方法，全是生肉

Wheel factorization：https://en.wikipedia.org/wiki/Wheel_factorization

Lenstra elliptic-curve factorization：https://en.wikipedia.org/wiki/Lenstra_elliptic-curve_factorization

Euler's factorization method：https://en.wikipedia.org/wiki/Euler%27s_factorization_method

Special number field sieve：https://en.wikipedia.org/wiki/Special_number_field_sieve

Dixon's factorization method：https://en.wikipedia.org/wiki/Dixon%27s_factorization_method

Quadratic sieve：https://en.wikipedia.org/wiki/Quadratic_sieve

Shanks's square forms factorization：https://en.wikipedia.org/wiki/Shanks%27s_square_forms_factorization

考虑之后有空了可以从中出几道题