-->
当前位置:首页 > 实验 > 正文内容

大素数生成演示实验

Luz4年前 (2020-12-30)实验2681
实验目的
  • 了解大素数的实现方法

  • 掌握大素数的基本原理

实验原理

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.实验工具
  信息安全综合实验系统

实验步骤
1

步骤1:大素数的生成

  1.1打开信息安全综合实验系统


图 1

  1.2打开“大素数生成”,开始大素数的生成实验,如图


图 2

  1.3选取四个16bits长度的素数p11、p12、p21和p22。

  • 这里我们分别填入值32771328435710733469


图 3

  1.4点击“计算p1并检验素性”,若不成功便重新选取p11或者p12,直至生成的p1为素数;


图 4

  1.5点击“计算p2并检验素性”,若不成功便重新选取p21或p22,直至生成的p2为素数;


图 5

  1.6点击“计算p并检验素性”,若不成功,系统会重新选取p22合成新的p2,直至生成的p为素数;


图 6

  1.7点击“随机生成64bit素数Q”,得到一个64bit素数Q;


图 7

  1.8点击“计算N并检验素性”,若不成功,系统会重新选取一个Q,直至生成的N为素数,筛选的次数会显示在计数器中;


图 8

图 9

  实验完毕。

本节考核

1.【填空题】素数的概念为一个大于1的自然数,除了1和它本身外,不能被其他自然数整除,请将最小的素数写出来2

答案解析:

正确答案:2

综合测验

1.【单选题】素数生成流程分为哪几个阶段阶段?

A、

素数搜索

B、

素数预筛选

C、

素数测试

D、

以上都是

答案解析:

正确答案:D

2.【单选题】好的搜索方法是提高素数生成速度的重要手段,常用的搜索方法有?

A、

随机搜索法

B、

随机递增搜索法

C、

A和B

D、

以上都不是

答案解析:

正确答案:C

3.【单选题】 下列哪些数字不是素数?

A、

-2

B、

2

C、

3

D、

以上都不是

答案解析:

正确答案:A

4.【单选题】素数生成流程分为哪三个阶段?

A、

素数判断、素数预筛选、素数测试

B、

素数搜索、素数预筛选、素数测试

C、

素数搜索、素数判断、素数测试

D、

素数搜索、素数预筛选、素数生成

答案解析:

正确答案:B

5.【单选题】欧拉定理是?

A、

任意一个数均可以被表示为若干个素数的乘积

B、

任意一个正整数均可以被表示为若干个数的乘积

C、

任意一个正整数均可以被表示为若干个素数的乘积

D、

任意一个正整数均可以被表示为若干个素数的和

答案解析:

正确答案:C

6.【单选题】费马小定理,若x是一个不能被质数p整除的整数,则xp-1-1必能被p整除。如果用同余式写法,公式的表达式是?

A、

@@x^{p-1}\equiv 1 mod p@@

B、

@@x^{p+1}\equiv 1 mod p@@

C、

@@x^{p-2}\equiv 1 mod p@@

D、

@@x^{p+2}\equiv 1 mod p@@

答案解析:

正确答案:A


发表评论

访客

◎欢迎参与讨论,请在这里发表您的看法和观点。