资源描述：
《信息安全基础综合实验讲义(最大公约与乘法逆元)-2012版》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第一部分数论基础实验1.3求解乘法逆元的算法实现求解乘法逆元的问题在现代密码安全中有着充分的应用和体现，尤其是现代公钥密码体制（例如RSA算法）的加密和解密的过程通常会涉及求解乘法逆元的问题。因此，掌握求解乘法逆元的算法对于学习现代密码学有着重要的现实意义。一、实验目的熟悉求解乘法逆元的算法，通过编程实现一种计算乘法逆元的算法，加深对求解乘法逆元方法的理解。二、实验原理【定义】对于整数a、m，如果存在整数b，满足abmodm=1，则称b为a模m的乘法逆-1元，记为a。【定理】a存在模m的乘法逆元的充要条件是a和m的最大公约数为1，记为gcd(a,m)=1。由定理可知
2、，当a与m互素时，a模m的乘法逆元有唯一解。如果a与m不互素，则-1a模m的乘法逆元a不存在。显然，如果a为素数，则1到a-1的任意整数都与a互素，即1到a-1的任意整数都有模m的乘法逆元存在。扩展欧几里德（ExtendedEuclid）算法是求解乘法逆元的常用方法。欧几里德（Euclid）算法用于计算两个整数的最大公约数，其原理是反复利用带余除法，直至余数为0时为止。两个整数的最大公约数可以用这两个整数的整系数线性组合的方式表示，扩展欧几里德算法就是计算整线性组合当中的系数，即计算gcd(a,m)=sNa+lNm中的整数sN，lN。扩展欧几里德算法除了可用于求解两
3、个整数的最大公约数外，还可以用于求解乘法逆元a-1。1.扩展欧几里德算法求解两个整数的最大公约数的Euclid_gcd(a,m)算法步骤描述如下：输入：两个整数a和m。输出：返回a和m的最大公约数。(1)u=1,g=a,v1=0,v3=m。(2)计算q=g/v3，t3=g%v3。(3)如果v3≠0，计算t1=(u-q*v1)modm,u=v1,g=v3,v1=t1,v3=t3。1(4)如果v3≠0，转到(2)。(5)返回g。-12.扩展欧几里德算法求解a模m的乘法逆元a的Euclid_inv(a,m)算法步骤描述如下：输入：一个整数a和m，其中m是模数。输出：返回a
4、模m的乘法逆元。(1)u=1,g=a,v1=0,v3=m。(2)计算q=g/v3，t3=g%v3。(3)如果t3≠0，计算t1=(u-q*v1)modm,u=v1,g=v3,v1=t1,v3=t3。(4)如果t3≠0，转到(2)；否则g=v3。-1(5)如果g≠1，返回a不存在；如果g==1，当v1>0时返回v1；当v1<0时，返回m+v1。【举例】求7关于96的乘法逆元。第一步：u=1,g=7,v1=0,v3=96。第二步：计算q=g/v3，t3=g%v3，即q=7/96=0，t3=7%96=7。第三步：计算t1=1-0*0mod96=1,u=0,g=96,v1=
5、1,v3=7。第四步：计算q=g/v3，t3=g%v3，即q=96/7=13，t3=96%7=5。第五步：计算t1=(0-13*1)%96=-13,u=1,g=7,v1=-13,v3=5。第六步：计算q=g/v3，t3=g%v3，即q=7/5=1，t3=7%5=2。第七步：计算t1=(1+1*13)%96=14,u=-13,g=5,v1=14,v3=2。第八步：计算q=g/v3，t3=g%v3，即q=5/2=2，t3=5%2=1。第九步：计算t1=(-13-2*14)%96=-41,u=14,g=2,v1=-41,v3=1。第十步：计算q=g/v3，t3=g%v3，
6、即q=2/1=2，t3=2%1=0。第十一步：g=1,v1=96–41=55。第十二步：返回v1=55。三、实验环境操作系统：Windows2000/XP/2003或以上版本。应用软件：VC++6.0或以上版本。四、实验内容和任务本实验要求学生掌握常用的求乘法逆元算法的实现方法，并运用高级程序设计语言完成一种求乘法逆元运算算法的程序，并通过具体运算测试函数的功能。表1-5给出采用扩展欧几里德算法求解乘法逆元的函数接口的定义，作为编程实现参考。扩展欧几里德算法的程序流程图如图1-8所示。2图1-8求解乘法逆元的程序流程图3表1-5乘法逆元函数接口函数long*euIn
7、v(longa,longm)功能计算a和m的最大公约数和a对于模m的乘法逆元输入a(待求乘法逆元的整数),m(模数)gcdInvOutArr[0]，它是a和m的最大公约数；输出gcdInvOutArr[1]，它是amodm的逆元，当该值为0时表示乘法逆元不存在。求解乘法逆元的界面实例如图1-9所示。输入a和m的值，点击“计算”按钮，计算最大公约数gcd(a,m)的值和乘法逆i的值。如果gcd(a,m)>1，则逆元不存在，此时乘法逆元i=0。点击“清空”按钮，可清空输入，以便重新输入测试值。图1-9扩展欧几里德算法界面【验证1】输入a=28,m=75,计算gcd(
