用于加密的超大素数是怎么得到的？
一般来说超大素数生成都是基于概率的素性检验演算法实现的。
这里的基于概率是指这个数可能极大概率是素数，也可能极小概率是合数；但是只要将后者的概率控制在一个非常小的范围内，就能将这个数当作大素数来使用。
一般的大素数生成流程简单的超乎想像，说白了就是挨个数试。试某个数是否是合数，如果是的话就试下一个数；如果不是的话就认定这个数是素数。值得一提的是，这种素数一般被称为伪素数；因为这些被演算法判定为非合数的数不一定是真的素数。
说的更清楚一点儿就是：这些演算法能够快速的确定大部分数是否是合数，但不能确定所有的数是否是合数；也就是不能确定某个数是否是真的素数。
有很多演算法可以实现快速的合数确认；有趣的是，这些演算法并不能确定合数的分解因子，但是就是能确认这些数是不是合数。
简单说一下比较常用的几个演算法。
第一个演算法是基于费马小定理的费马演算法。费马小定理是一个很有意思的定理，大意就是随便选一个素数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、椭圆曲线分解），来保证这个「素数」不太容易被分解。
推荐阅读：
