[問題] 想實作RSA,如何隨機產生大質數？ yuci PTT批踢踢實業坊

作者: yuci (vu03) 2016-01-19 00:31:40

最近想實作一次RSA，我使用C++開發，
預期是可以產生不限位數的金鑰，
目前大數運算都已經實作好了
就只差不知道如何找（產生）質數
在網路上看到的都是比較小位數的找法
想請問有沒有一些general rule可以產生大質數？謝謝

作者: a29813287 (ShyanWang) 2016-01-19 00:50:00

random大數以後再去做質數測試

作者: laladeer (laladeer) 2016-01-19 01:44:00

好像幾個質數相乘減一可以變成質數？

作者: LPH66 (-6.2598534e+18f) 2016-01-19 02:09:00

實務上做法都是一樓講的那樣, 那因為測質數的方法裡目前常見的是 Miller-Rabin 這種機率式測試法有機會(雖然可以任意小)讓非質數通過要實作的話要稍微注意這一點, 控制一下通過的機率(喔, 我指的是大數的質數測試, 因為顯然不可能用試除)

作者: yuci (vu03) 2016-01-19 20:14:00

謝謝大家，我本來是想問有沒有公式直接產生，看來只能用刪

作者: janice001 (真理) 2016-01-23 12:00:00

補充一下二樓說的做法是強質數的做法，這樣方法產生出來的質數被一些學者認為相對比較難破

繼續閱讀