基础算法实验

《基础算法实验》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、一、实验目的熟悉密码学编程平台和编程资源二、实验内容1.编程实现求两个整数的最大公约数的欧几里得算法2.编程实现求两个整数的最大公约数和线性组合的扩展欧几里得算法3.编程实现整数的模逆算法4.编程实现整数的快速模幕算法三、实验环境个人计算机，Java8平台对于非信息与计算科学专业的学生，可以选择任意编程平台编程实现整数的快速模幕算法四、实验记录与实验结果分析（注意记录实验中遇到的问题。实验报告的评分依据之一是实验记录的细致程度、实验过程的真实性、实验结果的解释和分析。如果涉及实验结果截屏，应选择白底黑字。）

2、1.欧几里得算法流程图如下：开始/输入r<—Mod(a.b)欧几里得算法程序为：functiong=Euclidean(“b)r=mod(a,b);while(r~=0)a=b;b=r;r=mod(azb);endg=b；end运行程序得到的结呆如厂CommandWindow»g=Euclidean(230,17)g=1>>g=Euclidean(6,3)>>g=Euclidean(2024,748)Z=44»g=Euclidean(748,2024)44A»1.线性组合的扩展欧几里得算法求解x,y的方法的

3、理解设a>bo1,显然当b二0,gcd(a,b)二a。此时x二1,y二0；2,ab<>0时设ax1+by1=gcd(arb);bx2+(amodb)y2=gcd(b,amodb);根据朴素的欧几里德原理有gcd(a,b)=gcd(b,amodb);则:ax1+by1=bx2+(amodb)y2;即:ax1+by1=bx2+(a-(a/b)*b)y2=ay2+bx2-(a/b)*by2;根据恒等定理得：x1=y2;y1=x2-(a/b)*y2;这样我们就得到了求解x1:y1的方法：x1,y1的值基于x2,y2

4、.上面的思想杲以递归定义的，因为gcd不断的递归求解一定会有个时候b二0,所以递归可以结束。function[x,y]=ExpandEuclidean(a,b)%其中gcd(a,b)=x*a+y*br=ones(1,2);r(l)=a;r(2)=b;i=0;while(r(i+2)〜=0)i=i+l;r(i+2)=mod(r(i),r(i+1));endn=i+2;xl=l;yi=o；fori=l:n/2x=yl;y=xl-fix(r(n-l-i)/r(n-i))*yl;xl=x;yi=y;endend运行

5、程序得到的结果如2CommandWindow>>[x?y]=ExpandEuclidean(2024打48)gcd(2024,748)=4419>>[]二ExpandEuc1idean(18,4)gcd(18?4)=2X=1y=-41.整数的模逆算法对于整数宫、P，如果存在整数b,满足甜modp二1,则说，b杲宫的模p乘法逆元。定理：3存在模p的乘法逆元的充要条件杲gcd(dp)二1程序：functionModularInversion(a,p)%求a模p的逆元，a

6、dean(a,p);ifg==li=l；while(mod(i*p+lra)~=0)i=i+l;endb=(i*p+l)/a;fprintf(乜模p的逆元b=%db);elsedisp(1a不存在模p的乘法逆7Lo1);endelsedisp(1a不存在模p的乘法逆元。1);endend运行结果如下:HowtoAdd创What'sNewCommandWindowa］国Sei...Name»Sb>>ModularInversion(2^4)a不存在模P的乘法逆元。>>ModularInversion(a

7、模p的逆元b=31>>ModularInversion(巌p的逆元b=3>>ModularInversion(a不存在模p的乘法逆元。>>ModularInversion(a不存在模p的乘法逆元。»47,91)2,5)2024,748)748,2024)1.实现整数的快速模幕算法对于它modn(x,k,n均为止整数)c当k为偶数时,xkmodn=[(x*x)modnf^nodn;当k为奇数时,dmodn=[(xmodn)(x)k~,mo

8、od7]5mod7=45mod7=[(4mod7i(44taod7)]mod7=[4((44)mod7)2]mod7=(42)mod7=4(2•2)lmod7=2Worksp...*□0X画■Sel・・・J“Name▲、王b3~P1result0运行结杲:CommandWindow>>result=ModuleOperation(5,10,7)result=2»result=ModuleOperation(3,5