為什麼 RSA 需要 p 和 q 是素數？
儘管已經閱讀了什麼使 RSA 通過使用素數來保證安全？，我尋求澄清，因為我仍在努力真正掌握RSA的基本概念。
具體來說，為什麼我們不能選擇非素數 $ p $ 和 $ q $ ?
我確實理解關鍵概念：將兩個整數相乘，即使是兩個非常大的整數也相對簡單。然而，對一個大整數進行因式分解是極其困難的，即使對於使用已知因式分解算法的電腦也是如此。
如果這是正確的，那麼 OP在這個執行緒中提出的原始問題繼續讓我感到困惑。Henrick 在這篇文章中的回答中的這一
部分包含相關資訊：
這也意味著，如果您要選擇 $ p $ , $ q $ 就像奇數一樣，你會讓自己更難找到 $ \phi(n) $ ，同時減小第二大素因子的相對大小，從而使其他人更容易因子 n。事實上，你和其他人一樣難以考慮 n，所以你會完全失去你的方案的陷門組件（如果不讓找到一對完全不可行的話 $ e $ , $ d $ ).
但我不明白為什麼我們讓自己更難找到 $ \phi(n) $ . 我相信這與以下事實有關：對於任何素數， $ n $ , 所有整數直到 $ n-1 $ 是相對優質的。如果整數不是素數，那麼我們實際上需要找出直到 n 的整數實際上是互素的。
我了解我們如何減小第二大素數的相對大小。例如： $ 10403 $ 有主要因數 $ [101,103] $ 儘管 $ 11000 $ 有主要因數 $ [2, 2, 2, 5, 5, 5, 11] $ .
所以，如果我理解正確的話，選擇一個非素數 $ p $ 和一個非素數 $ q $ 理論上可行，但問題是我們將創建一個更不安全的加密方案，因為：
- 非素數的乘積 $ p $ 和非素數 $ q $ 更容易因式分解（第二大素數小於如果 $ p $ 和 $ q $ 是素數）；
- 發現 $ \phi(n) $ 密鑰生成步驟變得更加困難，這會隨著上述安全性的降低而降低效率
對不起，如果這很明顯，但我是高等數學和程式的新手。我真的很想盡可能深入地理解這一點。
然而，對一個大整數進行因式分解是極其困難的，即使對於使用已知因式分解算法的電腦也是如此。
不是一概而論。如果一個大整數只由小因子組成，那麼分解一個大整數是微不足道的。
一個相當幼稚的分解算法
N如下：while N > 1: for p in increasing_primes: while p divides N: N = N / p factors.add(p)有了這個算法， $ 340 $ $ 282 $ $ 366 $ $ 920 $ $ 938 $ $ 463 $ $ 463 $ $ 374 $ $ 607 $ $ 431 $ $ 768 $ $ 211 $ $ 456 $ 可以準確計算 $ 128 $ 最裡面的while的迭代。（當然，這個數字是 $ 2^{128} $ )
一個合數的質因數越多，這些因數就必須越小。例如， $ 919 \cdot 677 = 622 $ $ 163 $ . 使用樸素算法，這需要 $ 157 + 1 = 158 $ 迭代因子。大小大致相同的數量由三個因素組成， $ 73 \cdot 89 \cdot 97 = 630 $ $ 209 $ , 只需要 $ 25 + 2 = 27 $ 迭代因子。
同樣，由兩個大小大致相等的因子組成的 1000 位數字大約需要 $ 10^{497} $ 迭代因子。由 100 個大小大致相等的因子組成的 1000 位數字大約需要 $ 434 $ $ 294 $ $ 481 + 99 \approx 10^{9} $ 迭代。由 1000 個大小大致相等的因子組成的 1000 位數字大約需要 $ 4 + 999 \approx 10^{3} $ 迭代。
因此，為了使分解盡可能困難，您希望素因數盡可能大，這意味著您希望 N 具有盡可能少的因數。和 $ p $ 和 $ q $ 主要， $ N $ 有兩個因素。和 $ p $ 和 $ q $ 合成的， $ N $ 至少有四個因素，可能更多。
請注意，這遠不是關於為什麼（我們認為） RSA 安全的完整答案，但我希望它給出一個更直覺/基於範例的為什麼 $ p $ 和 $ q $ 應該是素數。
另請注意 $ p $ 和 $ q $ 量級應該差不多。如果一個比另一個大得多，分解變得更容易。例如，如果 $ p = 43 $ , 樸素算法只需要 $ 14 $ 迭代。
（閱讀評論後（感謝Taemyr和Daz C），我更正了答案中的一些錯誤。主要觀點不受影響。）