要分解一個大數，先「猜」得準一點

先問：這在解什麼問題？the problem

整數分解問題（Integer Factorization Problem, IFP）是世上最難的問題之一——難的原因是運算能力有限。給定 N = pq（兩個質數的乘積），要有效率地求出 p 與 q 非常困難，這正是 RSA 安全性的基礎。

但作者提醒了一件事：隨著雲端運算的發展，有一些「脆弱的整數」其實是分解得掉的。而對於大小合適的 N，費馬演算法（Fermat's algorithm）可能是最簡單的求解方法之一。

怎麼做？EPF：先用連分數「估」出質因數the method

本文提出一個叫 EPF 的方法，用來估計一個合數的質因數。作者使用連分數（continued fractions）技術，輸出兩個整數 p_E+q_E 與 p_E−q_E，它們分別接近 p+q 與 p−q。

結果如何？results

作者證明 EPF 可以用來減少費馬演算法在分解一個合數之前所需的迴圈次數。並且明白指出：效果取決於質因數的大小。作者也認為 EPF 應該還有其他應用場景。