大素数生成演示实验

• 了解大素数的实现方法

• 掌握大素数的基本原理

1.素数定理
　　（1）欧拉定理
　　任意一个正整数均可以被表示为若干个素数的乘积。对于正整数n，假定p1，p2，p3，•••pk为其不重复的所有素数因子，则可表示为：
　　
　　显然，若n是素数p的k次幂，根据公式有：，因为除了p的倍数外，其他数都跟n互质。特别的是，如果n恰好是两个素数p和q的乘积，则 。
　　（2）费马小定理
　　若x是一个不能被质数p整除的整数，则必能被p整除。如果用同余式写法，就是。

2.素数生成
　　素数生成流程分为素数搜索、素数预筛选、素数测试三个阶段。
　　大素数的分布极不均匀，并且对一个大素数进行素性检测也是很费时，这使大素数进行素性检测也很费时，这使大素数的产生很慢。产生一个RSA密钥需将大部分时间都花在素数的寻找上，所以好的搜索方法是提高素数生成速度的重要手段。常用的搜索方法有随机搜索法和随机递增搜索法两种。
　　随机搜索法：随机产生一个技术p1进行素数测试，若是素数，则结束；否则，重新随机产生一个奇数p2进行素性测试，直到找到一个素数pt。
　　随机的证搜索法：随机产生一个奇数，对以该数为起点的技术依次进行测试，直至找到一个素数。

1.操作系统
　　操作机： Windows_7
　　操作机默认用户名： administrator 密码：123456

2.实验工具
　　信息安全综合实验系统