以毫秒為單位的最大數字
考慮將家用電腦/筆記型電腦用作執行任何分解算法的機器（例如典型的 2.4 GHz、16GB RAM、4 核處理器）。以毫秒為單位的主要因素中可以考慮的最大數字是多少？而是這樣的數字可能有多少位？
我們需要一點澄清或陳述一些合理的假設。例如，對於非常大的 n 值，可以非常快速地分解 2^n。我想這不是你要問的。您也可能不是在尋找嚴格的最壞情況，因為這取決於算法和實現。非平凡的隨機輸入可能需要時間。
“這可以是你的，每天只需幾美分*”（*：大約 64,000）。以毫秒為單位，我假設您的意思是 1-999 範圍內的某個值。
在我的電腦上，使用 Pari/GP 或 Perl/ntheory，查看平均時間，20 位半素數大約需要 1ms，隨機輸入大約是其中的 1/3。31 位的隨機輸入約為 10 毫秒，26-27 位的半素數。51 位的隨機輸入約為 100 毫秒，半素數約為 38-39 位。隨機輸入在約 60 位時達到 1000 毫秒。
這些程序很方便，但肯定不是最先進的因式分解。除其他外，它們僅使用 1 個核心。像 yafu 這樣的東西可能會是一個更好的基準，因為它的 SIQS 非常快並且使用多個核心。上次我檢查時，QS/NFS 交叉在 100-110 位範圍內，並且超過 1000 毫秒。
至於算法，在簡單的事情（例如試除法，甚至可能是一點點 Rho/Brent）之後，我們可能正在研究 ECM 或 QS。P-1 也可能在裡面。SQUFOF 對於 64 位輸入非常好，但對於良好的實現來說，這是亞毫秒級的時間，對於較大的輸入來說效果不佳。
這已經很老了，但早在 2009 年，我就對各種因式分解程式碼進行了一些測試。在本展示文稿的第 18 頁上，它顯示了使用 yafu 在 1 秒內將半素數分解為 55 位的可能位數。那是一個Q6600，yafu最新的程式碼可能也更快。