用於加密的超大素數是怎麼得到的？
一般來說超大素數生成都是基於概率的素性檢驗演算法實現的。
這裡的基於概率是指這個數可能極大概率是素數，也可能極小概率是合數；但是隻要將後者的概率控制在一個非常小的範圍內，就能將這個數當作大素數來使用。
一般的大素數生成流程簡單的超乎想像，說白了就是挨個數試。試某個數是否是合數，如果是的話就試下一個數；如果不是的話就認定這個數是素數。值得一提的是，這種素數一般被稱為偽素數；因為這些被演算法判定為非合數的數不一定是真的素數。
說的更清楚一點兒就是：這些演算法能夠快速的確定大部分數是否是合數，但不能確定所有的數是否是合數；也就是不能確定某個數是否是真的素數。
有很多演算法可以實現快速的合數確認；有趣的是，這些演算法並不能確定合數的分解因子，但是就是能確認這些數是不是合數。
簡單說一下比較常用的幾個演算法。
第一個演算法是基於費馬小定理的費馬演算法。費馬小定理是一個很有意思的定理，大意就是隨便選一個素數p，再選一個和p不成倍數關係的整數β，必然滿足β的p次冪和β對p同餘。
求一些類似於「0.999循環 等於 1」的有趣的或者是反常識的數學問題？
那麼這個命題的逆否命題就是，不滿足β的p次冪和β對p同餘的，p必然不是素數。
當然這個演算法侷限性還是很大的，因為你只能證明某個數不是素數，而無法證明某個數一定是素數。一個經典的偽素數就是561，還有1105和1729，這些「矇混過關」通過費馬演算法的偽素數被稱為Carmichael整數。
很不幸的是，這一類可以通過費馬演算法的偽素數有無限個。所以費馬演算法只適用於初步的簡單篩選。
第二個演算法是基於歐拉準則和勒讓德符號的Solovay-Strassen演算法。歐拉準則涉及一個平方剩餘的概念，不是很好描述。饅饅來。
首先先說平方剩餘。平方剩餘指的就是y2和x對奇素數p同餘，x＜p；這時候存在解y，稱x是模p的平方剩餘。
這說起來可能有點兒繞口，我們舉個簡單的例子：4的平方是16（y2=16），16除以11餘5（p=11，x=5），那麼就稱5是模11的平方剩餘。
有的數滿足這個條件，有的數不滿足這個條件。再舉個例子，取一個y2，y2除以11餘6（p=11，x=6）。我們說找不到這樣的數，則稱6為模11的非平方剩餘。
如果你很閑，把x從1到10算了一遍，就可以得到下述的式子：
12≡1，22≡4，32≡9，42≡5，52≡3，62≡3，72≡5，82≡9，92≡4，102≡1 （mod 11）
其中≡表示同餘符號。說通俗點兒就是前面的那個數除以11餘多少。比如72=49，49除以11等於4餘5。（4×11+5=49=72）
當你把這些數列出來之後，數一數x的值（也就是同餘符號右邊的那個值），你會發現一個很有趣的現象：這些平方剩餘，每個都不多不少，剛剛好有兩個。
譬如上面那個例子，剛剛好有兩個1，兩個4，兩個9，兩個5，兩個3。而剩下的2，6，7，8，10，剛剛好就沒有對應y的解，不是平方剩餘。
這就引出了一個歐拉準則：元素β是模奇素數p的平方剩餘的充要條件是，β的(p-1)/2次冪和1對p同餘。證明很簡單，既然設了β是平方剩餘，那麼β必然能寫成r2型。r2再(p-1)/2次冪，兩個2一約，就是r的p-1次冪，滿足費馬小定理，證畢。
那麼我們再說勒讓德符號。這個符號也很簡單，寫作(a|p)。若a是模p的平方剩餘，則(a|p)=1；若a不是模p的平方剩餘，則(a|p)=-1；若a和p是整除關係，則(a|p)=0。說白了就是a是不是模p的平方剩餘的一個判定式。
那麼我們終於可以說Solovay-Strassen演算法了。Solovay-Strassen演算法的核心就是：若n是一個素數，那麼勒讓德符號(β|n)≡β的(n-1)/2次冪，mod n。
這一定理的逆定理是不成立的，所以我們只能逐次的進行試驗。假設欲測試的大數是n，那麼隨機選擇一個整數β，計算(β|n)和β的(n-1)/2次冪，判定這二者是否同餘。假如不同餘，則說明未通過測試，該數為合數。假如同餘，則說明通過測試，繼續選擇另外一個β進行測試（因為素數一定可以通過同餘測試，但通過同餘測試的並不一定是素數），直到重複進行m次後結束。
簡單說一下這個定理是怎麼證的，他基於的是上面講過的歐拉準則。當β可以寫成平方剩餘r2時，勒讓德符號(β|n)=1，根據歐拉準則成立。當β不能寫成平方剩餘r2時，勒讓德符號(β|n)=-1，根據歐拉準則β的(n-1)/2次方和1對n不同餘。但是根據費馬小定理，β的n-1次方和1對n同餘。而根據平方差公式，
，而根據前面的歐拉準則，
無法被n整除，所以
必然能被n整除；進而得到
，證畢。
（說句題外話，答主原本不想插公式的……但是後來發現不用公式寫更特麼麻煩，扶額。嘛反正這段證明也不重要，看得懂就看，看不懂就直接看結論就好。）
而這裡面計算勒讓德符號(β|n)，可以通過二次互反快速得到；計算β的(n-1)/2次冪，可以通過快速求冪和模餘運算快速得到。結論就是不斷地重複選擇不同的β進行判定，當判定次數超過指定次數，得到非素數的概率很低的時候，就可以認為這個大數是一個素數。
第三個演算法是Miller-Rabin演算法，也是一個概率演算法。草率的寫一下流程吧，證明就不放了。
輸入待測試大數n，對n-1不斷地進行除2操作，直到得到一個奇數t。
於是這可以寫成
。顯然的，待測試大數n肯定是個奇數（廢話，是偶數還測個鎚子了），那麼n-1肯定是個偶數，故s≠0。
選擇隨機種子a，a＜n且與n互素。（這個也很容易做到，如果隨便一下子就測出來不互素，那就不用測了）
先設m=t。計算
：
——情況①：當
時，停機，輸出「n是一個合數」。
——情況②：當
時，停機，換一個隨機種子a再次進行測試。
——情況③：當
不成立時，重新設b為b2(mod n)，m為2m；繼續循環，直到得到情況①或情況②為止。
這個演算法比Solovay-Strassen演算法要來的快，重複選擇不同的隨機種子，很快就能得到一個概率很高的素數。不管怎麼說，這三個演算法都是基於概率的。在大家眼裡看起來精確無比的計算機，很多時候卻會執行基於概率的演算法——雖然這概率被反覆確認到很極端的程度；想想看也挺有趣的不是嗎？
以上。感謝您的閱讀。
有種素數叫做「工業級素數（Industrial-grade primes）」，定義是沒有經過嚴格數學證明、但是通過了「可能素數判定法」（比如米勒-拉賓判定法）的整數。用這種方法判定大整數是否是素數不是完全準確，但速度非常快，而且不會漏掉任何素數。
RSA加密法所需的大素數生成方式就很明顯了：隨機生成大整數，如果判斷這個數可能是素數，再用精確但速度慢的素數判定法來判斷這個數是否真的是素數。
How does OpenSSL generate a big prime number so fast??security.stackexchange.com9月26日更新：這篇來自StackExhange的回答表示，openssl庫生成超大素數仍然基於米勒-拉賓測試。在通過了64輪米勒-拉賓測試後，該數不是素數的概率已經下降到了2^-128，對於加密應用來說已經非常足夠了，沒有必要使用絕對正確但速度慢的AKS素數測試。
隨機生成一個奇數，然後用十輪miller rabin素性測試就差不多了，如果有強迫症的話，再多測試幾次，如果再再有強迫症的話，就再加上一次baillie-psw演算法測試一下，這樣，如果你想找合數通過的概率是almost impossible！加密的超大素數，一般用概率的演算法判定，因為概率的演算法出錯的可能性極低（比加密演算法被破解的可能性要低很多），且速度要快很多很多，而且實現演算法還比較簡單，確定性的演算法，比如aprcl或者橢圓曲線演算法，又慢實現又難，所以有理論意義，但是沒實際意義！mathematica軟體用的是baillie-psw演算法，至今也沒找到反例！
真的服了一羣不懂裝懂的人在那邊瞎評論
超大素數是怎麼得到的，之前已經有很多人講了，而且講了還蠻對
但是！
在其中一個還不錯的回答下面
看到了一個讓我很不爽的評論
真的，你們不懂，就不要裝懂好嗎？
尤其是這一條：
不僅誤人子弟，順帶還嘲諷別人
還RSA加密不是很難，看一看就懂
真不知道誰給你的自信？
@高飛車
我知道這個回答來晚了一點，但是你要的答案在這裡：
RSA的原理是：先確定一個數字n，再造兩個數a和b，使得：
且
至於為什麼需要兩個素數呢，只要是因為在造a和b的過程中會需要用到一個
這樣的東西，同時
。其中p、q就是x兩個素數
然後根據一堆奇奇怪怪的定理，你會發現當p、q是素數時，滿足條件的a和b具有如下性質：
回到問題，如果p、q是兩個合數，怎麼辦？
很簡單，按照程序，你依舊能夠算出這個
和
但是你有可能會發現你找不到a和b
或者你即使找到了a和b，也不滿足條件
換而言之，你的這個密鑰只能加密，不能解密
這是相當嚴重的後果！
不像某些人說的，只是破解概率相對大了點而已，順帶還嘲諷一下說RSA很簡單
來摸魚寫個比較完備的答案。。
首先由於素數的概率分佈，知兩個相鄰素數間的距離是O(log(n))的。對於生成一個譬如說是4096位數，我們取4096位一個隨機數身後比如連續20000個數，先用小素數篩一遍（這個過程甚至不需要高精度運算哦），然後對漏網之魚跑miller-rabin之類的概率reject composite的演算法。到最後積累了足夠高的confidence，就可以用了。
如果不太放心的話，可以1. 跑個快速的素性證明演算法。2. 跑個可以快速找出一些「相對小」因子的質因數分解演算法（如pollard rho、橢圓曲線分解），來保證這個「素數」不太容易被分解。
推薦閱讀：
