什麼是打破網際網路加密的人類最強數學「一般數體篩法（GNFS）」？
我們每天使用的網際網路。LINE 訊息、YouTube、Amazon 購物等，所有的通訊都受到「加密」保護。 目前世界上最廣泛使用的加密技術代表是「RSA 加密」。
RSA 加密防禦的核心非常簡單。它利用了 ** 「即使是電腦也無法解開巨大數字的質因數分解」 ** 這個數學特性。 例如，「15」我們馬上就知道是「3 × 5」，但一旦變成「270 位數的數字」，即使集結全世界的超級電腦，也需要耗費數億年才能解開。
然而，數學家們並沒有閒著。為了打破這道堅不可摧的密碼防線，人類創造了一種宛如魔法般的演算法（計算步驟），稱為 ** 「一般數體篩法（GNFS：General Number Field Sieve）」 ** 。
在這篇文章中，我們完全不使用專業術語，僅使用 ** 國中學到的數學（質因數分解、代數式、最大公因數） ** 知識，一步步徹底解說這個「人類最強演算法」破解密碼的原理！
第 1 章：破解密碼的目標是「國三的公式」
面對巨大質因數分解的最大必殺技。這就是在國三學到的這個公式。
** \(X^2 - Y^2 = (X + Y)(X - Y)\) **
你可能會想：「咦，這麼基礎的公式就能破解密碼嗎？」。然而，這正是解開一切的萬能鑰匙。
破解密碼的最終目標，對於一個巨大的數字 \(N\)，就是找到 ** 「將 \(X^2\) 和 \(Y^2\) 除以 \(N\) 後，餘數會相同的數字（\(X\) 和 \(Y\)）」 ** 。
為什麼「餘數相同」就能破解密碼？
假設有兩個數字 \(X^2\) 和 \(Y^2\)，它們「除以 \(N\) 的餘數相同」。 餘數相同代表著，相減後的 ** 「\(X^2 - Y^2\)」必定能被 \(N\) 整除（成為 \(N\) 的倍數） ** ，這是一個法則。
在這裡，我們假設用於加密的巨大數字 \(N\) 是由兩個秘密質數（\(p\) 和 \(q\)）相乘而成的（\(N = p \times q\)）。
將 \(X^2 - Y^2\) 因式分解後會變成 ** \((X - Y)(X + Y)\) ** 。 這成為 \(N\) 的倍數，意味著在這個乘法中的某處，隱藏著秘密質數 \(p\) 和 \(q\)。
奇蹟在此發生。 這兩個質數 \(p\) 和 \(q\)，有 ** 50%（二分之一） ** 的數學機率，會分開進入不同的房間： ** 「\(p\) 進入 \((X - Y)\) 的房間」和「\(q\) 進入 \((X + Y)\) 的房間」 ** 。
在只有質數 \(p\) 進入 \((X - Y)\) 房間的狀態下，讓我們計算 \((X - Y)\) 和 \(N\) 的 ** 「最大公因數（共通的最大零件）」 ** 。
- \((X - Y)\) 的內容 ＝ \(p \times\) 某個數字
- \(N\) 的內容 ＝ \(p \times q\) 共通的零件只有 ** 「\(p\)」 ** ！
也就是說，在計算出最大公因數的瞬間，隱藏的質數 \(p\) 就會掉出來，密碼就被完全破解了。（※最大公因數只要使用「輾轉相除法」，用手機也能瞬間計算出來）
** 【小專欄：為什麼是 2 次方？3 次方或 2 倍不行嗎？】 **
如果是「\(2X - 2Y\)」會變成 \(2(X - Y)\)，因為只有一個房間，所以無法將質數分開。如果是「\(X^3 - Y^3\)」，房間的大小會變得不平衡，計算會變得不必要的繁重。為了將質數漂亮地分開到兩個房間，「2 次方」是成本效益最高的。
第 2 章：如何尋找 X 和 Y？「收集質數卡片的拼圖」
目標已經很清楚了。但是，如果盲目地尋找「餘數相同的 \(X^2\) 和 \(Y^2\)」，直到宇宙毀滅也找不到。 因此，數學家們想出了一個被稱為 ** 「收集質數卡片的拼圖」 ** 的天才方法。
Step 1：只用篩子收集沙金（平滑數）
首先，準備一個適當的數字 \(Z\)，將其平方後除以 \(N\) 算出餘數 \(W\)。 （\(Z^2 = W\) 的餘數世界）
將得出的餘數 \(W\) 進行質因數分解。在這裡，只有當出現 ** 「只由 2、3、5、7 等小質數組成的 \(W\)」 ** 時，才將該算式作為「中獎卡片」保留下來，如果混入了大的質數就丟棄。 這就像在河裡用篩子過濾掉大石頭，只收集沙金一樣的作業。
Step 2：全部變成「偶數個」的拼圖
例如，假設收集到了以下 3 張沙金卡片。
- 卡片 A： \(Z_1^2 = 2^3 \times 3^1\)
- 卡片 B： \(Z_2^2 = 2^1 \times 5^1\)
- 卡片 C： \(Z_3^2 = 3^1 \times 5^1\)
我們將這些全部相乘。 右側會變成 \((2^3 \times 3^1) \times (2^1 \times 5^1) \times (3^1 \times 5^1)\)， 整理過後會變成 ** 「\(2^4 \times 3^2 \times 5^2\)」 ** 。
令人驚訝的是，質數的個數變成了「4 個、2 個、2 個」， ** 全部都是偶數個 ** ！ 全部都是偶數個，意味著只要將整體的數量減半，就會變成「某個東西的平方」。 也就是說，\((2^2 \times 3^1 \times 5^1)^2 = (60)^2\).
左側是 \((Z_1 \times Z_2 \times Z_3)^2\)，所以終於， ** \(X = (Z_1 \times Z_2 \times Z_3)\) ** ** \(Y = 60\) ** 這對期待已久的「\(X^2 = Y^2\)」組合就完成了！
對於電腦來說，計算質數個數「是偶數還是奇數（0 或 1）」的拼圖是它們非常擅長的，所以用這個方法就能高速找到 \(X\) 和 \(Y\)。
第 3 章：阻擋在前方的絕望之壁
這樣就能破解任何密碼了！……正當我們這麼想時，大問題發生了。 如果密碼數字 \(N\) 大約在「100 位數」以內，用這個方法（稱為二次篩法）是可以解開的，但當 \(N\) 變成「200 位數、300 位數」時，計算過程中出現的 \(W\) 就會變得太大。
數字一旦變得太大，「只由小質數組成的數字（沙金）」就不再出現。這變得比在沙漠中尋找隱形眼鏡還要困難，完全無法收集到解開拼圖所需的卡片。
這時候，人類的最終兵器 ** 「一般數體篩法（GNFS）」 ** 終於登場了。
第 4 章：人類最強的想法，創造「兩個世界」
GNFS 的天才發想是： ** 「因為只在現實世界中計算，所以數字才會變得巨大。那麼，我們就用多項式（代數式）創造一個『裏世界』，將計算的負擔分散成兩半吧。」 **
代數式的魔法
GNFS 使用一個基準數字 \(m\)，將巨大的數字 \(N\) 轉換成代數式。 例如如果 \(N=100\)，設 \(m=4\)，則 \(100 = 4^3 + 2(4^2) + 4\)。 使用字母 \(x\) 將其變成 ** \(f(x) = x^3 + 2x^2 + x\) ** 這個算式（裏世界）。
這個算式有趣的地方在於，它具有 ** 「只要將字母 \(x\) 代入 \(m\)（在上面的例子中是 4），隨時都能瞬間移動回到現實數字 \(N\)」 ** 的特性。
在兩個世界中同時尋找沙金
GNFS 製造出許多隨機的整數對 \((a, b)\)，並同時進行以下兩個計算：
- ** 現實世界 ** ： \(a - b \times m\)
- ** 代數式的世界 ** ： 依照代數式規則計算 \(a - b \times x\) 的值
藉由將問題分成兩個世界，處理的數字大小會戲劇性地變小（變輕）。這就像是把巨大的岩石劈成兩半，變成容易處理的石塊一樣的概念。
然後，我們用篩子過濾，只收集那些在 ** 「現實世界和代數式的世界中，兩者都是『只由小質數組成（沙金）』」 ** 的奇蹟整數對 \((a, b)\)。這就是「數體篩法」名稱的由來。
密碼終於被破解的瞬間
當從兩個世界收集到數千萬張「沙金卡片」後，就會使用超級電腦的巨大矩陣計算，找出在第 2 章做過的「質數個數全部變成偶數的組合」。
找到組合後，
- 將現實世界中產生的平方數設為 ** \(X^2\) **
- 將代數式世界中產生的平方算式設為 ** \(Y(x)^2\) **
最後，將代數式 \(Y(x)\) 中的 \(x\) 代入 \(m\)，使其瞬間移動到現實世界並會合。 這樣一來，宛如數學魔法般， ** 「\(X^2\) 和 \(Y^2\) 的餘數相同」 ** 的狀態就嚴格地完成了！
接下來只要按照第 1 章的說明，計算 \(X - Y\) 和 \(N\) 的最大公因數，堅不可摧的 RSA 加密就會應聲瓦解，秘密質數也將隨之現身。
結語：數學永無止境
你可能會想：「太好了，只要用 GNFS 就能破解任何密碼了吧！」。 然而，RSA 加密也沒有認輸。目前網際網路上使用的是被稱為「RSA-2048（約 617 位數）」這種怪物級的巨大數字。
儘管 GNFS 號稱是人類最強的演算法，但要解開 270 位數（RSA-270），據說即使將全世界的電腦連線在一起，也需要數千年甚至數萬年。就目前而言，我們的 LINE 或銀行資料還是安全的。
不過，如果出現了 ** 「能瞬間找出任何巨大數字 \(X\) 和 \(Y\) 的魔法」 ** 會怎麼樣呢？ 事實上，最接近這個存在的，就是目前正在開發的 ** 「量子電腦（Shor 演算法）」 ** 。數學上已經證明，只要利用量子力學波的特性，就能無視麻煩的卡片收集拼圖，一次就抽出正確答案。
製造密碼的人（防禦）與製造破解密碼演算法的人（攻擊）之間，無止盡的鬥智。 當你知道國中學到的「質因數分解」和「代數式」，其實是在世界資安最前線激烈交鋒的武器時，是否覺得數學課變得稍微有趣一點了呢？
發現未來最強演算法的人，或許就是正在讀這篇文章的你！
(※本文為了讓中學生能理解，將密碼破解的數學魅力概念化。實際的 GNFS 是使用了代數體的理想類群、同態映射等高等大學數學來進行嚴格計算的)