關於拆分與分解
在《應用密碼學手冊》的第 89 頁備註 3.5 上，寫了以下內容：
一個非平凡的因式分解 $ n $ 是形式的因式分解 $ n = ab $ 在哪裡 $ 1 < a < n $ 和 $ 1 < b < n $ ; $ a $ 和 $ b $ 據說是不平凡的因素 $ n $ . 這裡 a 和 b 不一定是素數。為了解決整數分解問題，研究分裂的算法就足夠了 $ n $ ，即找到一個非平凡分解 $ n = ab $ . 一旦發現，因素 $ a $ 和 $ b $ 可以測試素數。然後可以遞歸地將用於拆分整數的算法應用於 $ a $ 和/或 $ b $ ，如果發現其中任何一個是複合的。以這種方式，質因數分解 $ n $ 可以獲得。
我認為這種論證是有缺陷的。在寫這本書的時候，沒有有效的素數測試可用（或者至少沒有在書中給出，但據我所知，這些測試中的第一個是 2002 年的 AKS 算法），所以聲明
一旦發現，因素 $ a $ 和 $ b $ 可以測試素數。
對我來說沒有意義，因為在本書的上下文中無法有效地完成素數測試。我有什麼問題嗎？
編輯：
我知道像 Solovay-Strassen 或 Miller-Rabin 這樣的機率素數測試當時已經存在，它們也包含在書中。但是我不明白為什麼 Miller-Rabin 的存在應該是一個可以有效完成素數測試的論點，因為當返回“n 是素數”時，所述測試有一個錯誤界限。根據多項式歸約的定義（再次取自第 88 頁的書：
定義讓 $ A $ 和 $ B $ 是兩個計算問題。 $ A $ 據說polytime減少到 $ B $ , 寫 $ A \le_P B $ ，如果有一個算法可以解決 $ A $ 它使用作為子程序的假設算法來求解 $ B $ ，並且如果算法為 $ B $ 做。
如果我正確理解了這個定義，我們就不能在論證中使用米勒拉賓作為素數測試 $ \text{factoring} \le_p \text{splitting} $ 上面，從那以後我們不能確定我們找到的因子確實是素數。（如果我沒記錯的話，如果算法能給出 100% 準確的答案，就可以說它可以解決問題。）
我希望我的意思很清楚，如果不是，請告訴我，我會重新提出我的問題。
Miller-Rabin至少從 1980 年就為人所知（根據維基百科）。儘管它是機率性的，但它已經足夠好了。例如，openssl 使用它 $ ^\textrm{1} $ . 手冊的第 4 章討論了各種素性檢驗，這可能會讓您更好地理解作者的想法。
$ ^\textrm{1} $ 請參閱bn_prime.c的原始碼