实验报告填写说明1.每门实验课程均应按本格式完成实验报告。2.实验报告要求双面打印。3.学生应在做完实验后指定时间内完成实验报告，交指导教师评阅。4.学生必须依据实验指导书，提前预习实验目的、实验基本原理、实验内容及方法。5.教师将在实验过程中抽查学生预习情况。6.在课程全部实验项目完成后，分班级按学生学号将各实验项目报告装订成册，并附实验课程成绩汇总表，交课程承担单位（实验中心或实验室）保管存档。信息安全中的数学方法与技术课程实验报告学号姓名专业班级实验题目欧几里德算法实验类型□演示型□验证型□设计型□综合型实验目的1.掌握欧几里徳算法，并会运用其求出两数的最大公约数；2.掌握求解冋余方程的方法会对其求解；3.分别会对其进行c语言进行编程。实验内容使用VC++编程语言设计实现一个算法程序，要求包括以下部分：1)欧几里德算法求a,b的最大公因数gcd(a,b)和满足gcd(a,b)=as+bt的整数s和t；当a=3378,b=231时，求出相应的gcd(a,b)及s,t.2)求解同余方程ax三b(modn)其中n>0.当a=987,b=564,n=2005,求出x.实验原理欧几里得算法求最大公约数欧几里德算法又称辗转相除法，用于计算两个整数a,b的最大公约数。其计算原理依赖于下面的定理：定理1：gcd(a,b)=gcd(b,amodb)定理2：假设a,b且a>b.由除法原理我们知存在h0,r0使得a=bh0+r0,其中r00,则存在h1,r1使得b=r0h1+r1，其中r10,则存在h2,r2使得r0=r1h2+r2,其中r20,则存在h2,r2使得r0=r1h2+r2,其中r2#includevstdlib.h>#includevstring.h>intGCD=0;voidmain(){//求整数a和b的最大公因子inta=0;intb=0;printf("请输入整数a的值:\n");scanf("%d",&a);printf("请输入整数b的值:\n");scanf("%d",&b);if(a<0)a=-a;if(b<0)b=-b;if(a==011b==0){if(a+b==0){printf("整数a和b无最大公因子!\n");exit(0);}elseif(a==0&&b!=0){printf(”最大公因子(a,b)=%d\n",b);GCD=b;}elseif(a!=0&&b==0)源代码ints0=1;intsi=0;intt0=0;inttl=1;ints2=s0;intt2=t0;ints,t,a1,r2;while(r1!=0)al=rO/rl;r2=rO-a1*r1;s2=sO-a1*s1;t2=tO-a1*t1;s=s1;t=t1;rO=r1;r1=r2;sO=s1;s1=s2;tO=t1;t1=t2;if(a>b)printf("sa+tb=s*%d+t*%d=(a,b)=%d\n所以s=%d,t=%d\n",a,b,GCD,s,t);exit(O);}elseif(a<=b){printf("sa+tb=s*%d+t*%d=(a,b)=%d\n所以s=%d,t=%d\n",a,b,GCD,t,s);源代码2.求解同余方程ax三b(modn)实验代码：#includeviostream>structtriple{intgcd,x,y;}；intmod(inta,intb)〃取模运算amodb{if(a>=0)returna%b;elsereturna%b+b;}tripleex_Euclid(inta,intb)〃扩展欧几里德算法，求最大公约数和x、y使得x*a+y*b=(a,b){tripleresult,temp;if(b==0){result.gcd=a;result.x=1;result.y=0;}else{temp=ex_Euclid(b,mod(a,b));result.gcd=temp.gcd;result.x=temp.y;result.y=temp.x-(a/b)*temp.y;}returnresult;}voidMLCE(inta,intb,intm)〃线性同余方程ax三b(modn)求解源代码{tripletemp=ex_Euclid(a,m);if(b%temp.gcd!=O){printf("方程无解\n");return;}intx=mod(temp.x*b/temp.gcd,m/temp.gcd);〃满足方程的最小的非负整数if(temp.gcd==l)printf("方程有1个解属于[0,%d):\nx=%d\n",m,x);else{printf("方程有%d个解属于[0,%d):\n",temp.gcd,m);for(inti=O;ivtemp.gcd;i++)printf("x[%d]=%d\n",i+1,x+i*m/temp.gcd);}}intmain(){inta,b,m;scanf("%d%d%d"，&a,&b,&m);MLCE(a,b,m);system("pause");return0;}实验结果1.求最大公约数实验结果截图如下:■C\Us&rs\Adi11in由廿日1£|叭1?&51（1甲\信底安主敦学基社的12亍宾验VDebuUl启沖幘输人整数“的值=3378尉人整数b的值：hsi冠金因子匕“=2*a.+th-B**33?8+七吨3丄一(aj-b>一3pffts=-8,t=11?|?pess且nykeytocontinue2.求解同余方程ax三b（modn）实验结果截图如下：■'C:\USBrs\Administrator^DesktopVfF.BS^M^®Si的12个实验\0訪旳\1・熬^7875642B05万程有I个解属于r0-2005＞：x-287请按任意键£瞬-••总分:评分小项分值得分1.实验报告格式排版10分2•实验设计思路（科学性、可行性、创新性）30分3•实验代码编写（规范性、正确性、复杂性）30分4•实验结果分析（正确性、合理性）20分5.实验心得总结10分实验总结实验成绩评定
