密碼學筆記 - Pollard's p - 1 Algorithm

假設我們有一個合數 $n$，其中存在一個質因數 $p$。
Pollard's p - 1 algorithm 是一種在 $p - 1$ 的最大質因數很小時，能有效分解 $n$ 的演算法。

這個方法常被應用在 CTF 題目中，用來分解 RSA 公鑰中的 $n$，進而破解 RSA。

費馬小定理與分解的核心原理

根據 費馬小定理：
若 $a$ 不是 $p$ 的倍數，則：

進一步來說，對某個 $k$ 有：

所以：

這個值一定會是 $p$ 的倍數——如果剛好等於 $p$，那我們就成功找到一個非平凡因數了！

Pollard's p - 1 實作邏輯

演算法的關鍵就是去構造一個剛好是 $p - 1$ 倍數的指數。實作時，我們通常固定 $a = 2$（只要 $p \ne 2$，上述推論都成立）。

接著，我們會嘗試計算如下：

• $\gcd(2^1 - 1, n)$
• $\gcd(2^{1 \times 2} - 1, n)$
• $\gcd(2^{1 \times 2 \times 3} - 1, n)$
• $\gcd(2^{1 \times 2 \times 3 \times 4} - 1, n)$
• ⋯⋯

這個指數其實就是階乘 $k!$，也就是我們試圖讓 $k!$ 包含 $p - 1$ 的所有質因數。

當某個 $k$ 滿足 $p - 1 \mid k!$ 時，就有很大機會使得：

這樣我們就能成功分解 $n$ 啦。

使用條件

當 $p-1$ 最大的質因數很小，可以有效的分解合數 $n$

Python 程式碼

import math

def pollard(n):
    a, b = 2, 2
    while True:
        a, b = pow(a, b, n), b + 1
        d = math.gcd(a - 1, n)
        if 1 < d < n:
            return d