質因數分解：方法、應用和加密的關聯

發布於 2026/04/14 · 閱讀約 5 分鐘

每個大於 1 的整數都可以唯一分解成質數的乘積 — 這叫做算術基本定理。60 = 2² × 3 × 5，沒有其他分法。

短除法範例：分解 360

360 = 2³ × 3² × 5

實用應用：GCD 和 LCM

• 最大公因數 GCD：取共同質因數的最小次方。GCD(12, 18) = GCD(2²×3, 2×3²) = 2×3 = 6
• 最小公倍數 LCM：取所有質因數的最大次方。LCM(12, 18) = 2²×3² = 36
• 公式：GCD(a,b) × LCM(a,b) = a × b

加密的關聯

RSA 加密（網路安全的基石）仰賴一個事實：把兩個大質數相乘很快，但要把結果分解回去極其困難。

• 7 × 13 = 91 → 容易
• 91 的質因數是？→ 需要試試 → 7 和 13
• 當數字有 600 位數時，目前最強的電腦也要幾百萬年才能分解