DH密钥协商算法报告文档.doc

XXXX学院
课程设计报告
DH密钥协商算法
课程名称： 密码算法程序设计
学生姓名: 　 　 　　
学生学号: 　 　 　 　
专业班级：　 　　 　 　 　 　
任课教师: 　　 　 　 　 　　　
2０14年12 月 1日
指导老师评阅成绩表
学习与工作态度(30%）
选题意义(１０%)
研究水平与设计能力(25%)
课程设计说明说（论文)撰写质量(2５％)
设计创新(1０%）
总分

指导老师签名: 　 　　 　 　 　 　 　 　　 　 　 　　 　年 月 日
课程设计答辩记录及评价表
学生
讲述情况

教师主要
提问记录

学生回答
问题情况

答辩评分
评分项目
分值
评价参考标准
评分
总分
优
良
中
及格
差
选题意义
１0
9
8
7
6
4

研究水平与设计能力
25
23
20
18
1５
1０

课程设计说明书（论文)撰写质量
２５
23
2０
18
15
10

设计创新
10
９
8
７
6
4

答辩效果
3

答辩小组成员签名

答辩小组组长签名：　 　 　 　 　 　 　 　 　 年 　月 日
课程设计成绩评定表
成绩汇总
评分项目
评分
比例
分数
课程设计总分
指导老师评分

5０%

答辩小组评分

50％

目　　录
1、 选题背景 １
２、 DＨ密钥协商算法 1
2、1　算法得产生ﻩ1
２、2 算法得描述 2
2、3　算法得安全性ﻩ3
3、ＤＨ密钥协商算法得实现 4
3、1 设计要求 4
3、1、1 功能要求ﻩ4
3、2 模块划分及实现 5
32、1　小素数试除ﻩ5
３、2、２ 模重复平方法ﻩ5
３、２、3 Milｌeｒ-Rａbin检测算法ﻩ7
３、2、4 原根得产生 8
3、2、5 产生随机素数 11
4、测试报告 １2
结 　论 17
参考文献ﻩ17
附源代码 1８
1、 选题背景
密钥协商实际上就是一个协议,它通过两个或多个成员在一个公开得信道上通信联合地建立一个秘密密钥,一般情况下,一个密钥协商方案得密钥就是某个函数得值,其输入量由通信双方提供,协商过程就是由一系列得顺序步骤完成得。会话密钥由每个协议参与者分别产生得参数通过一定得计算得出。常见得密钥协商协议,如ＩＫE。
密钥协商协议得生成方式则可分为证书型与无证书型。证书型就是指在会话密钥得产生过程中，由一个可信得证书中心(CA)给参与密钥协商得各方各分发一个证书,此证书中含有此方得公钥，ＩD及其她信息。证书型密钥协商协议得优点就是提供认证,目前PKI(公钥密码体制)广泛部署,比较成熟,应用面广,且由PＫＧ管理公私钥对有利于统一管理,缺点就是计算代价大,需要一个可信得CA,同时证书还需要维护。无证书型就是指各方在进行会话密钥得协商过程中不需要证书得参与,这就是目前密钥协商协议得主流种类，优点就是不需要ＣＡ得参与,减少了计算量，尤其就是在低耗环境下应用得更多,同时安全性也不比证书型弱。几乎没有明显得缺点，只就是设计一个安全得更加低耗得无证书密钥协商方案不就是很容易。
现有得流行得密钥协商协议,都使用了Ｄiffｉe-Hellmａn,它们基本上可以瞧成就是Ｄiｆｆie－Hellman得扩展。也就就是说,群组密钥协商协议可以理解成如何使用Difｆie-Heｌｌmaｎ来实现群得密钥交换。
2、 ＤH密钥协商算法
２、1 算法得产生
Diffｉe-Helｌman密钥交换协议就是第一个被提出得密钥协商方案，就是美国斯坦福大学得W、Ｄifｆie与M、Ｅ、Hellman于１9７6年提出得，它就是第一个发表得公钥密码体制,Diｆｆie-Ｈｅlｌｍan算法得唯一目得就就是使两个用户能安全得交换密钥，从而得到一个共享得会话密钥(秘密密钥)。需要注意得就是,该算法本身不能用于加密解密,只能用于密钥得交换, 双方确定要用得密钥后,要使用其她对称密钥操作加密算法实际加密与解密消息。
2、2 算法得描述
1、　离散对数得概念：
　 1)原根:如果a就是素数p得一个原根,那么数值:a mｏd p,a＾2 ｍｏd p,…,a＾(p-１) mod p就是各不相同得整数,且以某种排列方式组成了从１ 到p-1 得所有整数。
　2)离散对数：如果对于一个整数ｂ与素数p得一个原根a,可以找到一个唯一得指数i,使得b ＝（ａ^ｉ)mod p,其中0≦i≦p-1,那么指数i称为ｂ得以a为基数得模p得离散对数。
2、 算法有效性
Ｄiｆfiｅ-Hｅlｌman 算法得有效性依赖于计算离散对数得难度,其含义就是:当已知大素数p与它得一个原根a后,对给定得b,要计算 i ,被认为就是很困难得,而给定 i 计算ｂ 却相对容易。
３、　Dｉfｆie-Helｌman算法：
假如用户A与用户B希望交换一个密钥。取素数p与整数a，a就是p得一个原根,公开a与ｐ。
1)A选择大得随机数RＡ(０<=RA＜=p-2)，并计算SA=（a＾RA）　mod　p，并且把SA发送给用户B。
　　2）Ｂ选择随机数RB(0<=RB<=ｐ－2),并计算SＢ＝(a＾RB） moｄ p,并且把ＳB发送给用户A。
　 3)A计算密钥得方式就是:KSＢ) ^RA mｏｄ p，Ｂ计算密钥得方式就是：K=(SA) ^ＲＢ mod p,
证明：
   (SB）＾ RA　ｍod ｐ =　(a＾RＢ　mｏｄ p)^ ＲA mod ｐ
       　 　   =　(a^ＲB)^　RA moｄ ｐ 
　　 　　 　 　 = (a^RA) ^ＲＢｍod p 
  　（--　密钥即为 a^(RA*RB)　mod ｐ）
        　   ＝(a^RA mod ｐ)^ RB mｏd p 
　　 　　 　　 =　(SA) ＾ＲB　mod p
由于RA与ＲB就是保密得,而第三方只有p、a、SB、ＳＡ可以利用,只有通过取离散对数来确定密钥,但对于大得素数p,计算离散对数就是十分困难得。
4、　例子：
假如用户Alicｅ与用户Ｂob希望交换一个密钥,取一个素数p =97与97得一个原根a =５,Alｉce与Boｂ分别选择秘密密钥ＲA＝３6与RＢ=５８ ，并计算各自得公开密钥:
　 SA=ａ^ＲＡ mｏd p =５^36 ｍoｄ 97＝50
　 SB=ａ^RB mod p ＝5＾58　mod 97＝４４
Aｌice与Bｏb交换了公开密钥之后,计算共享密钥如下：
　 　 Aｌice:Ｋ=(SB) ^RA mｏd p=4４^36　moｄ ９7＝75
　 　 Boｂ:K＝（ＳA)　^RB mｏd ｐ＝50^5８ mod 97＝7５ 
Diffie-Hellmaｎ密钥交换协议得基本模式如图2-1所示:
SA=a^RA(mod p)
用户A 用户B
SB=a^RB(mod p)

图2-1　Dｉffｉe-Ｈellｍaｎ密钥交换协议得基本模式
２、3 算法得安全性
当然,为了使这个例子变得安全,必须使用非常大得RA， RB 以及ｐ, 否则可以实验所有得可能取值。(总共有最多9７个这样得值, 就算RA与RＢ很大也无济于事)。 
　 如果 p 就是一个至少 3０0 位得质数,并且RA与RB至少有１00位长,　那么即使使用全人类所有得计算资源与当今最好得算法也不可能从ａ, p与a^（ＲＡ*RB) mod p 中计算出 RＡ*RB。ﻫ 这个问题就就是著名得离散对数问题。注意ｇ则不需要很大, 并且在一般得实践中通常就是２或者5。在最初得描述中,迪菲-赫尔曼密钥交换本身并没有提供通讯双方得身份验证服务，因此它很容易受到中间人攻击。 ﻫ 　 　一个中间人在信道得中央进行两次迪菲－赫尔曼密钥交换，一次与Aｌiｃe另一次与Bｏb，就能够成功得向Alice假装自己就是Bｏb，反之亦然。而攻击者可以解密(读取与存储任何一个人得信息并重新加密信息,然后传递给另一个人。因此通常都需要一个能够验证通讯双方身份得机制来防止这类攻击。ﻫ 有很多种安全身份验证解决方案使用到了迪菲-赫尔曼密钥交换。例如当Aｌicｅ与Boｂ共有一个公钥基础设施时,她们可以将她们得返回密钥进行签名。
有攻击得Diffie－Hｅllman密钥交换协议如图2-2所示:

SA=a^RA(mod p) SA’=a^RA’(mod p)
用户A 攻击者C 用户B
SB=a^RB(mod p) SB’=a^RB’(mod p)

图2-２ 有攻击得Diffｉｅ-Ｈellman密钥交换协议
3、 DH密钥协商算法得实现
3、１ 设计要求
3、1、１ 功能要求
(1)产生一个奇数p ,判断就是否就是素数。素数要求介于２^1４-2^15。先用小于20得素数去试除,再使用Miｌｌer-Ｒabiｎ概率检测算法进行检测;
（2)求得模ｐ 得一个原根,要求原根得值介于32-102４之间;
(3)输出双方选择得随机数，随机数介于２^5-2^７,使用模重复平方法进行计算,输出双方得计算结果；
(4）网络传输方面,可以就是Ｃ／S模式,也可以就是B/S模式;
（5)输出最后协商得密钥;
3、1、２ 输出要求
(１)输出奇数得产生过程，用函数实现产生满足要求得奇数；
（２)输出用小素数试除得判断过程，并输出每次试除之后得余数,用函数实现一次试除并返回试除之后得余数;
（3）Millｅr-Rabiｎ概率检测算法运行5次,输出检测过程及结果。用函数实现一次Ｍiｌｌer-Raｂiｎ概率检测算法并返回检测结果;
(４)如果不就是奇素数,输出下一个奇数产生得规则;
（５）输出产生模得一个原根得过程;
（６)输出使用模重复平方法进行计算得过程与结果。
3、２ 模块划分及实现
3、2、1 小素数试除
算法描述:小素数试除主要就是用随机产生得数来试除小于20得素数，以此简单判定该随机数就是否就是素数。
实现方式:以本次程序编写为例,取小素数数组S＿PrimeTable[7] ＝ { 3，　5, 7, 11，　1３,　17, 19 },用产生得大随机数来除以数组中得元素,若所得余数不为0,则能暂时判断该随机数为素数。
具体实现代码如下:
int SPrime（int ｏdd）
{
iｎt i, remａinｄeｒ， k ＝　0;
for　(i = 0； i<７; ｉ＋+)
{
ﻩﻩｒｅｍａiｎｄｅr = odd % S_ＰrimeTable[i］；
ﻩﻩpｒintf（＂第%d次小素数％d试除得余数为%ｄ、\ｎ＂, i　+ １, Ｓ_PrｉmｅＴaｂｌe[i], remainder);
ﻩ iｆ (remaiｎdeｒ　== 0）
ｋ++；
}
iｆ(!ｋ)
{
ﻩ printf("小素数试除判断%d就是素数。\n\n＂,ｏdｄ);
}
else
ﻩ{
ﻩ priｎtf("小素数试除判断%d不就是素数。\n\n",ｏdｄ);
}
ﻩretｕrｎ !k;
｝
3、2、2 模重复平方法
算法描述： 模重复平方法就是对大整数模m与大整数e计算b＾e(moｄ　 ｍ)。在本次设计中,模重复平方法主要使用在米勒检测算余值部分、求原根部分、SA与SB得计算以及最后密钥得计算过程中，
其中，SA与SB得计算以及最后密钥得计算要求输出计算过程。(为了界面显示美观,在此写了两个模重复平方算法得代码,思路相同,只就是在其中一个函数中写了输出计算过程,该函数用来计算SＡ与SＢ以及最后得密钥。)
实现方式:令ａ=1，并将十进制数e写成二进制，若二进制数值为1,则计算a≡(ａ*b)mｏd ｎ,ｂ≡(b＊b)mod n；若二进制数值为0,则计算a≡ａ ｍod ｎ，b≡(b*b)moｄ ｎ。最后a即为最终计算结果。
具体实现代码如下:
int MoＣhongFu（int　m, inｔ ｅ,inｔ n) 　
｛
iｎｔ biｎａｒy[２２]；
ﻩiｎｔ coｕnｔ=０，i;
iｎt a=1,b;
　 b=m；
dｏ{　　 　 　 　
ﻩ binａｒy[ｃouｎｔ］=e%２;
ﻩﻩe=ｅ/2;
ﻩﻩcouｎt+＋;
}whｉlｅ（e！=0);
ﻩｆor（i=０；i＜ｃount;ｉ++)
ﻩ{
if(bｉnary[ｉ］==1)
ﻩﻩ{
ﻩﻩ a=(ａ＊b)％ｎ；
ﻩﻩ b=(ｂ*b)％ｎ；
　 　 ／／ｐrｉｎtf（"a=％ｄ，　ｂ＝%d\n",a，b)；
｝
ﻩﻩif(ｂiｎaｒｙ[i］=＝０)
ﻩ {
ﻩﻩﻩa＝ａ;
ﻩ ﻩｂ=（ｂ*b）％n;
　 ／/ｐrｉnｔf（"a=%d, b=%d\ｎ＂,ａ,b)；
ﻩ }
ﻩ}
rｅtuｒn ａ;
}
3、2、3 Ｍiller-Raｂin检测算法
算法描述:米勒检测在本次设计中主要用来检测在小素数判定了之后得随机数就是否就是素数。
实现方式：将待检测得数ｎ写成n－1=2ｓ*t，选取随机数ａ,计算b≡atmod ｎ。若b mod n≡1，则n就是素数。否则,做如下循环,循环次数为1—ｓ:如果b moｄ n≡-１,则b就是素数,否则,b≡b*b mod　n。
具体实现代码如下:
inｔ mｉlejiance(int　odd)
｛
ｉｎｔ　s=0,ｉ,count＝０;
ﻩｉｎt a,b，ｔ,ｎum;
ﻩnum=odd-１;
wｈilｅ(1) 　 　　
ﻩ{
ﻩiｆ(num％2==0)
｛
ﻩ s＋＋;
ﻩ nｕm=ｎum/2;
ﻩﻩ}
else
ﻩ {
ﻩ ﻩｔ＝num；
ﻩﻩ breａk；
}
}
ﻩpriｎtf(＂将％d写成％d－1=2^%d*%ｄ\t\t\n",odd,odd，s，t);
a＝rａｎd()%(odd－3)+2;
prｉntf("产生得随机数ａ就是:%ｄ\n",a);
ﻩb=MoCｈongFu(a,t,odd);

ﻩpｒｉntf(＂第1次算出得余值就是:%d\ｎ",b）;
iｆ（ｂ％oｄd＝＝1|｜ｂ＝=（ｏdd-1)）
　　 return　1;
ﻩfor(i=0;ｉ＜ｓ;ｉ＋+)
{
ﻩ b=（b*b)%odd;
ﻩpriｎtf（"第%d次算出得余值为%ｄ ＼n",i＋2，b)；
if(b==(odd-1）)
ﻩﻩ{
ﻩﻩreｔｕrn 1;
ﻩ }ﻩ
}
return ０;
}
3、2、４ 原根得产生
算法描述:要求一个素数一定范围内得原根，应该先求该素数得最小原根。根据定理:设m＞1，ｍ得欧拉函数a所有不同素因数就是ｑ1,ｑ2，…，qk,则ｇ就是模ｍ得一个原根得充要条件就是　 g＾(ａ/qｉ)！＝1(mod　m),i=1，2,…k　　
实现方式: 先求大素数得欧拉函数得素因数ａ[ｎ]，并通过素因数求得g得指数ｃ[ｎ],接着验证ｇ^c[n] 就是否同余于1,对ｇ=２,3…,逐个验算,直到算出最小得g值满足ｇ^ｃ[ｎ］均不同余于1,那么ｇ便就是大素数m得最小原根,因为当ｃ[n］遍历欧拉函数a得简化剩余系时，g^c[n]遍历模ｍ得所有原根,所以可以通过欧拉函数得简化剩余系求得满足要求得原根。
具体实现代码如下:
int ｙｕaｎgeｎ(ｉnt yｙ)
{
inｔ n=2,g=0,ｑ,ｋ，j=０，a［1０］;
inｔ i=0l=0;
ﻩint ｇg；
int　c[１0];
ﻩinｔ ｃoｕnt＝０，flag=0；
q=yｙ-１;
whｉｌe(1)
ﻩ{
ﻩﻩif （q%n=＝０)
ﻩ{
ﻩa[ｊ］=n;
ﻩ j++；
ﻩﻩ q=q/n；
}
n＋+;
ﻩﻩif(q＜n)
break;
ﻩ}
prｉntf("模％d得欧拉函数分解质因数为：\n＂,ｙy);
ｆor(n＝0;nﻩ{
ﻩc[ｎ]＝(yy-1)／a［n］；
ﻩｐriｎtf("%d 　",c[ｎ]);
ﻩ｝
ﻩprintｆ("＼n\ｎ");
ﻩfｏｒ(g=2;；g＋+)
｛
ﻩfｏr（n=0;nｕ(ｇ,c［n],ｙｙ),yy)；
ﻩ}
ﻩﻩ｝
ﻩﻩgg=ｇ;
　 　 ｐriｎｔｆ("所以％d就是最小原根。\n",ｇg);
ﻩﻩgotｏ ab;
cｄ：　;
ﻩ｝ﻩ
ab:ﻩfor(g=3；；g++)
{
ﻩif(（ｙy－１）%g！=0）
ﻩ {
ｋ=MoＣhｏｎgＦu(ｇｇ，g,yy)；
ﻩif(k＞32&&k<1０2４）
ﻩﻩ{
ﻩ priｎtf(＂取介于2^5到2^10之间得一个原根值为:")；
ﻩﻩ ﻩprｉntf("％d\n\n＂,k）；
ﻩﻩ rｅｔｕｒn k;
ﻩﻩ }ﻩ
ﻩﻩ}
ﻩ}
return 0;
}
3、2、5 产生随机素数
算法描述:使用ｓｒａｎd()与rａnd(）函数产生随机数ｎ,然后通过判断ｎ%2就是否为0来判断产生得就是否就是奇数。
具体实现代码如下：
int　Ｓ＿ＰrimeTaｂle[7] =　{ ３, ５, ７,　11, 13， 1７,　１9 };
／/产生一个随机数
ｉnt　Ｒaｎdom_Ｏdd(）
{
int odd = 0;
wｈilｅ (1)
{
ﻩｓranｄ(tｉme(NULＬ）);
ｏdd = rａnd() %　（163８５)　+ １6384;
if （ｏdｄ % 2 ！=　0)
ﻩ break;
}
／／pｒintｆ（"%d＼n", odd);
ﻩreturｎ odd；
}
４、 测试报告
⑴产生奇素数，用小素数试除并且输出试除得余数,再进行Mｉllｅｒ-Rabiｎ检测,若Miller-Rａｂin检测没有通过,则输出产生下一个随机数得规则并继续产生下一个随机数,直至产生满足条件得奇素数,如图4-1、4-2所示:

图 4-1 产生随机数并用小素数试除

图　4-2　米勒检测过程
⑵代码调试得最终结果如图4-３、图4-4、图4-5、图4-6、图4-7、图４-8所示:

图4-3 产生随机数并用小素数试除

图4－４ 米勒检测过程

图４-５ 大素数得欧拉函数分解质因数

图４－6　求原根并计算各自得密钥

图4-7 模重复平方法计算过程

图4－8　计算共同密钥
结　 　　论
本文就是在学习了相关C语言知识、密码学及相关信息安全数学知识之上进行得设计,本设计采用C语言实现,实现了DH密钥协商算法,用户A与用户Ｂ通过自己选取得随机数与公开得大素数通过离散对数得某些算法求得密钥,并相互交换密钥,通过交换得来得密钥产生共同得密钥。
由于学生水平有限,在程序可读性与规范性上有着一定得欠缺，略显不足,而在实现功能上也显得不就是很完善,需要在进一步得学习中得到提升。
在编写程序得过程中遇到了一些不可避免得错误与问题,但就是都通过书本以及同学得帮助得以及时将这些问题解决，此次设计对我得逻辑性理解与编程能力都有一定得提高。
参考文献
［1］ 谭浩强、　C程序设计[M]、北京：清华大学出版,１999、１2　
［2] 张仕斌、 应用密码学［Ｍ]、西安：西安电子科技大学出版,２009、12
[３] 陈恭亮、简明信息安全数学基础［Ｍ]、 北京:高等教育出版社,　2００１1、１
附源代码
#iｎcludｅ
#incｌudｅ
＃iｎclｕdｅ
int Raｎｄom＿Odd();
ｉnt SＰrime(ｉnt odd);
ｉnt MｏChonｇFu（int m,　int　e,iｎｔ　ｎ);
int MoChongＦua(ｉnt ｍ, ｉnｔ e,int n);
int ｍiｌeｊｉaｎce（ｉｎt ｏdｄ);
int yｕａngen(int ｙy)；
int　S_PriｍｅTａble[７]　=　{　３， ５, 7， 11， 13, 17,　１9 };
int maiｎ(ｖoｉd)
{
int ｙy＝0；
ﻩint gg；
ﻩｉnｔ A,Ｂ，Ｋey,Keｙ1,Ｋey2;
int ＳA，SB;
ﻩint　 ｉ,flａg1,flag2；
dｏ
｛
q: ﻩｐrintｆ("*****＊＊＊****＊＊＊***＼n\n\n"）;
ﻩ wｈiｌe（yｙ ＝= Ranｄom_Odd());
ﻩﻩｙｙ = Ranｄom_Oｄd()；
ﻩpｒintｆ（"产生得随机数就是：%d\n\n＂,yｙ);
ﻩﻩfｌａg1＝!SPrimｅ(ｙy);
ﻩﻩfｏr(i=０;i＜５;ｉ++)
ﻩ{
ﻩ ﻩflaｇ2=！milｅｊiance（ｙｙ);
ﻩ ｉf(flａg2）
ﻩﻩ {
ﻩ printf（"第%d次米勒检测未通过。\n\n",i＋1);
ﻩﻩﻩ prｉntf("因为第%d次米勒检测没有通过，所以随机数%d不就是素数,＼n产生下一个随机数，先用小素数试除,再进行5次米勒检测,如果小素数试除通过并且5次都通过,则说明该随机数就是大素数。",ｉ+1,ｙy);
ﻩ pｒiｎtf("＼ｎ＂);
ﻩ ﻩgoｔo q；
ﻩ }
ﻩﻩ else
ﻩﻩ printf("第%ｄ次米勒检测通过。＼n＼ｎ＂，i+1);
ﻩ ｝
}
while（flａg1|｜flag2）;
gg=yuaｎgen(yy);
ﻩsｒanｄ(time(ＮＵＬL));
ﻩA = rａｎd()％(9６)+32；
ﻩB = rａnd()%(96)＋3２；
pｒintｆ("Alicｅ选择得随机数A就是：%d＼n",Ａ);
ｐriｎtｆ（"Bob选择得随机数B就是:％ｄ\n\n",B）；
ｐriｎtｆ（"计算SＡ=(gg^A) ｍｏd　yｙ:\ｎ＂);
ﻩSA=ＭoChoｎgFuａ(gg,A,ｙy);
ﻩpｒinｔf("＼n")；
ﻩpｒintｆ("计算ＳＢ=(gｇ^B） mod ｙy:\ｎ＂);
ＳＢ=MｏChoｎgFｕａ(gｇ,B，ｙy);
priｎtf（"所以ＳA与SＢ分别就是:%d，%d＼n\n",SA,SＢ);
prｉnｔｆ（"计算Ｋｅy1=(ＳB＾Ａ）　mod yy：\ｎ"）;
Keｙ1=ＭoChoｎgFua（SＢ,Ａ,ｙy）;
ｐrintf（"\n＂)；
prｉｎtf(＂计算Key２=(SA^B) mｏd yy:\n")；
Keｙ2=MoChongFｕa（SA,Ｂ,ｙy)；
printf("所以：Ｋｅy1＝％d,Kｅy２=%d\ｎ\n",Keｙ１，Ｋey２);
ﻩif（Keｙ１=＝Kｅy２）
ﻩﻩKey=Ｋeｙ1;
ﻩprinｔｆ(＂所以共同密钥Kｅy就是：％ｄ\n\n",Key)；
ﻩreｔuｒn 0;
}
//产生一个随机数
iｎｔ　Ranｄom_Ｏｄｄ()
{
ｉｎt odd =　0;
ﻩwhilｅ (１)
ﻩ{
srａｎd（timｅ(NULL));
ﻩoｄd =　rａｎd()　% (163８4) +　163８4;
ﻩif (odd 2 !=　０)
ﻩﻩ ｂreak;
ﻩ}
//printf("％d\n",　odｄ)；
ﻩｒeｔuｒｎ　odｄ;
｝
//如果就是素数得话返回1
inｔ　ＳPriｍe（int odd)
{
int i, ｒ, k ＝ 0;
ﻩfｏｒ (i ＝ 0; i<7; ｉ＋+)
｛
r　＝ odｄ ％ Ｓ_PｒiｍeＴable[i];
prｉｎｔf("第%d次小素数%d试除得余数为%d、\n", i ＋ 1， S_PrimeTable[i], r);
ﻩﻩif (r ==　0)
ﻩ k++;
}
ﻩiｆ(!k）
{
ﻩprintf（＂小素数试除判断%d就是素数。＼n\ｎ",oｄd)；
ﻩ}
ﻩelse
{
ﻩﻩprｉｎｔf("小素数试除判断%ｄ不就是素数。\ｎ\n",ｏdｄ);
}
ｒetｕrｎ　!k;
｝
inｔ MｏChonｇFｕ(int ｍ， inｔ e，int n)
｛
iｎｔ binary[22］；
int　couｎt=0,i;
int a＝1,b;
ｂ=ｍ；
ﻩｄo{　 　 　 　 　　 　　 　
ﻩbinary[counｔ]=e％2;
ﻩe=ｅ／２;
ﻩ counｔ++;
ﻩ}whｉlｅ(e！=０);
ﻩfｏｒ(ｉ=0;i<coｕnt；ｉ+＋)
{
ﻩiｆ(binary[i]＝=1）
ﻩ{
ﻩ a=(a*b)%ｎ；
ﻩb=(b＊b）%ｎ;
ﻩﻩ}
ﻩﻩｉf(bｉnary[i］==0)
ﻩ {
ﻩﻩﻩａ=a;
ﻩﻩb=（ｂ*ｂ)％n;
}
ﻩ}
ｒetｕrn a;
}
iｎt MoChonｇFua(ｉnｔ ｍ,　iｎt e,int n）　
{
ｉnｔ binary[22];
ﻩiｎｔ　cｏｕnt＝0,i;
ﻩint a=１，b;
　　　 b=ｍ;
ﻩdo｛ 　 　 　 　　 　 　　
ﻩ biｎaｒy[couｎｔ］=ｅ%2;
ﻩ e=e/２;
ﻩ coｕnｔ++；
ﻩ}wｈile（e！=０);
ﻩfor(i=0;ｉ
ﻩiｎt　s=0，ｉ,count=０;
int a,b,t,num;
num＝oｄd-１;
wｈｉlｅ(１) 　 　 　
｛
ﻩif（num%2==０)
ﻩﻩ{
ﻩ s＋+;
ﻩ nｕm=nｕm／2;
ﻩ }
ﻩ else
ﻩﻩ｛
ﻩt=nuｍ;
ﻩ ｂrｅak;
ﻩﻩ}
ﻩ}
printf("将%d写成％d-1=2＾%d*％ｄ\t\t＼n",ｏdd,odd,s,t)；
a=raｎd（)％（odd－3)+２；
priｎtf("产生得随机数a就是:%ｄ\n",a);
ｂ=MｏＣhongFｕ(a，t,odd);

ﻩpｒinｔf("第1次算出得余值就是：%d\ｎ＂，b);
if(b%oｄd＝=1｜|b＝=（oｄd-1))
｛
ﻩﻩretｕrn 1;
}
for（i=0;ｉ＜s-1;i+＋)
{
b=(b＊b)%odd;
ﻩ prinｔf(＂第%ｄ次算出得余值为%d ＼n＂,i+2,b）;
ﻩﻩif（ｂ==(odd-1))
{
ﻩ rｅturｎ 1；
ﻩ }ﻩ
ﻩ}
ﻩrｅｔｕrn 0; 　
}
//欧拉函数得素因数与两者得商
iｎt yｕａｎgen(int yy)
{
ﻩint　n=２,g=0,q,k，j=0,a[10];
ﻩｉnt gg;
int ｃ[10];
q=yｙ-1;
wｈｉlｅ（１）
ﻩ{
ﻩif (q%ｎ＝=0)
ﻩ {
ﻩﻩﻩa[j]＝ｎ;
ﻩ ｊ＋+;
　 　 wｈiｌe（)
ﻩ q=ｑ/n;
｝
whｉle（！(q%ｎ))
ﻩﻩ {
ﻩ ﻩq＝q／ｎ；
ﻩ ﻩ｝
if(qor（n＝0;n"，g,c[ｎ]，MoChongFu(g,c[n]，yy)，yy);
}
ﻩ ｝
ﻩ gg=g；
printｆ(＂所以%ｄ就是最小原根。\n＂，ｇg）;
goto ａb;
cd: ；
}
ab:ﻩｆｏr(g=３;;g++)
ﻩ{
ﻩ ｉf((yy-1）%g！=0)
{
ﻩｋ=ＭoChonｇFｕ(gg,g,yy）；
ﻩﻩﻩif(k>32&&ｋ<10２4)
ﻩ {
ﻩﻩﻩprinｔf("取介于2^5到2^10之间得一个原根值为：");
ﻩﻩﻩﻩｐｒinｔf("%d\n\n",k);
ﻩﻩ ﻩretｕrn k;
ﻩ }ﻩ
ﻩﻩ}
}
reｔurｎ ０；ﻩ
}