rsa 加密实践
1.产生一个随机数在2的l次方跟2的l+1次方间，用Miller-rabin测试它是否是一个素数。
2.给出x和n，用扩展的欧几里得算法计算x的逆y（mod n）。
3.调用上面的两个函数，产生ras参数n=p*q，e和d。
4.给出信息M，用你产生的参数加密。检查你加密的正确通过解密。
2021-12-19 10:30:15
2KB
1
费马素性检验是一种随机化算法，判断一个数是合数还是可能是素数。
根据费马小定理：如果p是素数，1 \le a \le p，那么
a^ \equiv 1 \pmod。
如果我们想知道n是否是素数，我们在中间选取a，看看上面等式是否成立。如果对于数值a等式不成立，那么n是合数。如果有很多的a能够使等式成立，那么我们可以说n 可能是素数，或者伪素数。
在我们检验过程中，有可能我们选取的a都能让等式成立，然而n却是合数。这时等式
a^ \equiv 1 \pmod
被称为Fermat liar。如果我们选取满足下面等式的a
费马素性检验
费马素性检验
a^ \not\equiv 1 \pmod
那么a也就是对于n的合数判定的Fermat witness。
整个算法可以写成是下面两大部：
输入：n需要检验的数；k：参数之一来决定检验需要进行的次数。
输出：当n是合数时，否则可能是素数：
重复k次：
在[1, n − 1]范围内随机选取a
如果an − 1 mod n ≠ 1 那么返回合数
返回可能是素数
2021-10-18 16:10:12
2KB
1
本代码采用C语言，基于vc6.0+miracl5.5.4。运用费马小定理和概率性算法对大整数的素性检测（大整数从txt文档读入）
2019-12-21 19:34:58
2KB
1