應該是使用機率演算法來測試一個數是否是素數的吧。由素數定理（Prime number theorem），可以估計某個範圍內的素數密度，也就是你隨機找一個數是素數的機率。另外，需要一些測試素數的演算法來完成它是否真的是素數這樣的判定（Primality test）。像Miller這樣的素數測試，在機率上表現得就很好（實際上對於大整數來說，這個過程的主要的時間複雜度應該在乘法上的消耗）。中文wiki的條目上就有金鑰生成的一些簡短的說明呢。RSA加密演演算法

只能被1和本身整除的數叫質數，例如13，質數是無窮多的。得到兩個巨大質數的乘積是簡單的事，但想從該乘積反推出這兩個巨大質數卻沒有任何有效的辦法，這種不可逆的單向數學關係，是國際數學界公認的質因數分解難題。 R、S、A三人巧妙利用這一假說，設計出RSA公匙加密演算法的基本原理：1、讓計算機隨機生成兩個大質數p和q，得出乘積n；2、利用p和q有條件的生成加密金鑰e；3、透過一系列計算，得到與n互為質數的解密金鑰d，置於作業系統才知道的地方；4、作業系統將n和e共同作為公匙對外發布，將私匙d秘密儲存，把初始質數p和q秘密丟棄。 國際數學和密碼學界已證明，企圖利用公匙和密文推斷出明文--或者企圖利用公匙推斷出私匙的難度等同於分解兩個巨大質數的積。這就是Eve不可能對Alice的密文解密以及公匙可以在網上公佈的原因。 至於"巨大質數"要多大才能保證安全的問題不用擔心：利用當前可預測的計算能力，在十進位制下，分解兩個250位質數的積要用數十萬年的時間；並且質數用盡或兩臺計算機偶然使用相同質數的機率小到可以被忽略。