信息安全技术作业-扩展欧几里得算法编写求解乘法逆元

欧几里德扩展算法求多项式乘法逆元在数学的世界里，有个东西叫多项式。

说白了，它就是由变量和常数构成的一种数学表达式，像是“3x^2 + 2x + 1”这种。

不说你可能觉得没什么，实际在很多地方都用得到。

可你知道吗，有些时候我们需要找一个“逆元”，就像在生活中找个朋友互相帮助一样，互相成就。

这个时候，欧几里德扩展算法就会派上用场了。

想象一下，你和朋友一起去超市买东西，你们有各自的预算，结果买完东西一算，发现你们花的钱总和正好就是你们的预算。

多开心啊！可要是其中一个人花了超出预算，怎么办呢？这时候就需要“逆元”了。

简单来说，逆元就像是你花的那些钱的“反向操作”，让你又回到最开始的预算上。

数学里的逆元就是要找到一个多项式，让它和原来的多项式相乘，结果等于1。

这听起来是不是有点复杂？但实际上，跟朋友一起合作，互相帮助一样，找到这个逆元其实也能挺有趣的。

在多项式的世界里，欧几里德扩展算法就像是个聪明的智者，帮我们找到这个逆元。

先说说什么是欧几里德算法。

其实很简单，它就是一种求最大公约数的方法。

想象一下，你有两个数字，一个是你家里的小狗的年龄，另一个是你奶奶的岁数。

你想知道它们的最大公约数，也就是两者共同的“朋友圈”有多大。

用欧几里德算法，你可以一步一步把大数字变小，最后找到那个共同的“朋友”。

可是，等到多项式的世界里，事情就有点不同了。

你得用扩展版的欧几里德算法，毕竟这里的“朋友”不止两个。

有了多项式，怎么求逆元呢？得设定一个模，比如一个素数，这样就能在这个范围内找到逆元。

想象你在打麻将，得有个圈子才能玩下去，不然大家都不知所措。

咱们就开始动手了。

先用欧几里德算法找出原多项式和模之间的关系。

这就像你和朋友打扑克，先得把牌理顺，看看谁的牌大。

然后用扩展算法，逐步找出每一步的系数，像是记录下你们在超市里每一项开支，最后再加起来，找出最终的结果。

这个过程其实挺有趣的，像是在玩一场智慧的游戏，时不时还会有意想不到的收获。

欧几里得算法与扩展欧几里得算法（求二元一次不定方程、乘法逆元）1.欧几里得算法，即辗转相除法。

用于求两个整数的最大公约数比较方便，时间复杂度为O（logN）N为两个整数的规模。

最大公约数，是能够同时被两个整数整除的最大整数。

比如说，求56和21的最大公约数：（每行数分别代表a=56,b=21,a%b）此时得到最大公约数为7。

递归代码如下：int gcd(int a, int b)return b ? gcd(b, a%b) : a;2.扩展欧几里得算法顾名思义，扩展欧几里得算法就是对欧几里得算法的扩展，可以应用于求二元一次方程的通解、乘法逆元等。

对于上面的欧几里得算法，当递归到出口时，a=7,b=0。

很容易就可以得到一组ax+by=7的解：x=1,y=0。

那么如何通过7x+y=7的解逆推出56x+21y=7的解呢？对于欧几里得算法的每一个状态，都存在ax+by=gcd(a,b)的解，我们假设有这样两组解（且他们为相邻状态）：ax1+by1=gcd(a,b)a'x2+b'y2=gcd(a',b')那么可以知道：a'=b b'=a%b 且gcd(a',b')=gcd(b,a%b)=gcd(a,b)，所以有ax1+by1=bx2+(a%b)y2 另a%b可写为 a-a-b所以有 ax1+by1=bx2+(a-(a-b)b)y2故ax1+by1=ay2+bx2+(a-b)by2故ax1=ay2 by1 = b(x2+ (a-b)by2)故 x1=y2 y1 = x2 +(a-b)y2故可以得到x1,y1与x2,y2的关系 : x1=y2 y1 = x2 +(a-b)y2我们已知的是最后一组解，那么就要根据最后一组解逆推上去，就可以得到ax+by=gcd(a,b)的一组解了。

代码如下：int exgcd(int a, int b, intx, int y)return a;int r = exgcd(b, a%b, x, y); --递归到求出公约数，开始倒着求每一组的x,y。

扩展的欧几里得算法扩展的欧几里得算法是一种求解最大公约数的算法，也被称为扩展欧几里得算法或扩展辗转相除法。

它不仅可以求出最大公约数，还可以求出一组使得两个数的线性组合等于最大公约数的系数。

本文将介绍扩展的欧几里得算法的原理、应用及其优化。

一、原理扩展的欧几里得算法是基于欧几里得算法（辗转相除法）的扩展。

欧几里得算法是一种求解最大公约数的方法，其基本思想是：用较小的数除较大的数，再用余数去除除数，如此反复，直到余数为零为止。

最后的除数就是最大公约数。

例如，求出48和18的最大公约数，过程如下：48 ÷ 18 = 2 (12)18 ÷ 12 = 1 (6)12 ÷ 6 = 2 0因此，最大公约数是6。

扩展的欧几里得算法的主要思想是在欧几里得算法的基础上，求出一组使得两个数的线性组合等于最大公约数的系数。

设a、b为两个正整数，d为它们的最大公约数，那么必定存在整数x和y，使得ax + by = d。

扩展的欧几里得算法就是通过辗转相除的过程，递归求解x和y的值。

具体来说，假设a、b为两个正整数，d为它们的最大公约数，且a > b。

则有：1. 如果b = 0，那么d = a，此时x = 1，y = 0。

2. 如果b ≠ 0，那么可以将a除以b，得到a = bq + r（其中q为a÷b的商，r为余数）。

因为d是a和b的公约数，所以d也是b和r的公约数。

因此，可以递归地求解b和r的系数x1和y1，即有：bx1 + ry1 = d由于a = bq + r，可以将其代入上式，得到：bx1 + (a - bq)y1 = d展开后得到：ay1 + b(x1 - qy1) = d因此，x = y1，y = x1 - qy1。

通过递归求解，最终可以得到x和y的值，从而求出a和b的最大公约数d以及一组使得两个数的线性组合等于最大公约数的系数。

二、应用扩展的欧几里得算法在密码学、数论、计算机图形学等领域都有广泛的应用。

用扩展欧几里得算法求乘法逆元例题扩展欧几里得算法是计算两个整数的最大公约数的算法，并且可以根据最大公约数得到一组解，用于求解线性同余方程的解，也可以用来求乘法逆元。

下面以求解$a$的乘法逆元为例，即寻找一个整数$x$，使得$a times x equiv 1 (text{mod} p)$，其中$p$是一个质数。

使用扩展欧几里得算法，先计算$a$和$p$的最大公约数$gcd(a,p)$，假设为$d$，则有：$gcd(a,p) = d = ax + py$，其中$x$和$y$是扩展欧几里得算法得到的一组解。

由于$d$是$a$和$p$的最大公约数，所以$d$必定是$a$的约数，即$d|a$。

同时，由于$p$是质数，所以$d$不可能是$p$的约数，即$d$与$p$互质。

因此，我们可以将等式两边同时除以$d$，得到：$dfrac{a}{d}x + dfrac{p}{d}y = 1$由于$d$与$p$互质，所以$dfrac{p}{d}$的乘法逆元存在，假设为$k$，即$dfrac{p}{d} times k equiv 1 (text{mod} d)$。

将$k$乘到等式两边，得到：$dfrac{a}{d} times k times x + dfrac{p}{d} times k times y = k$由于$dfrac{p}{d} times k equiv 1 (text{mod} d)$，所以可以将$dfrac{p}{d} times k$替换为$z$，得到：$dfrac{a}{d} times k times x + z times y = k$这个等式可以看成是一个线性同余方程$dfrac{a}{d} times k times x + z times y equiv k (text{mod} d)$，使用扩展欧几里得算法求解即可得到$x$的值。

总结一下求乘法逆元的步骤：1. 使用扩展欧几里得算法计算$a$和$p$的最大公约数$gcd(a,p)$，得到一组解$x$和$y$，使得$gcd(a,p) = ax + py$。

扩展欧几里得算法：欧几里得算法中，计算x, y 的最大公约数的方法是辗转相除，例如：gcd (26, 15)26 % 15 = 1 (11)15 % 11 = 1 (4)11 % 4 = 2 (3)4 % 3 = 1 (1)3 % 1 = 3 0可知，gcd (26, 15) = 1如果gcd(x, y) = r，那么有ax + by = r，可以看出，上面的步骤实际上是可以直接得出a, b 的：null26 % 15 = 1 ... 11 => 11 = 26 - 15 1 1 -115 % 11 = 1 ... 4 => 4 = 15 - 11 = 15 - (26 - 15) = -26 + 2*15 1 -1 211 % 4 = 2 ... 3 => 3 = 11 - 4*2 = (26 - 15) - (-26 + 15) * 2 = 3*26 -5*15 2 3 -54 % 3 = 1 ... 1 => 1 = 4 - 3 = (-26 + 2*15) - (3*26 - 5*15) = -4*26 +7*15 1 -4 73 % 1 = 3 0在每一轮，我们都可以得到一个模的表达式为：ri = aix + biy如果不考虑第一轮和第二轮，那么ai 和bi 可以表示为(qi 为每一轮得到的商)：a i = a i-2 - q i * a i-1b i = b i-2 - q i * b i-1证明如下：输入：x,y,则有如下：x/y=q1…..r1 =>r1=x-q1*yy/r1=q2…r2 =>r2=y-q2*r1=y-q2*(x-q1*y)=-q2*x+(1+q2*q1)*y r1/r2=q3…r3 =>r3=r1-q3*r2=(x-q1*y)-q3*(-q2*x+(1+q2*q1)*y)=(1+q2*q3)x+(-q1-q3*(1+q2*q3))*y则可以看出有：a3=1+q3*q2=a1-q3*a2B3=b1-q3*b2由此可以推测出：a i = a i-2 - q i * a i-1b i = b i-2 - q i * b i-1但是a1,b1,a2,b2比较特别：a1=1=a-1 – q1*a0b1=-q1=b-1 – q1*b0由此我们可以知道a-1=1,a0=0,b-1=0,b0=1即可满足。

分数的模运算在ECC加密算法中需要用到对分数的模运算，但大多的资料只给结果没有给计算过程，就连初等数论书上面也找不到计算方法，搜索了一下，终于在网上找到了相关资料，用的思路其实还是整数模运算的，直接copy下来下面是“分数”模运算的定义：b, m互质（互为素数）k = a/b (mod m) <=> kb = a (mod m)这里求x = 1/17 (mod 2668)<=>17x = 1 (mod 2668)<=>17x = 2668k + 1 （k∈整数）取合适的k使得17|(2668k+1) 【应该是17能被(2668k+1)整除,也即17x mod 2668 = 1】这里刚好17 | (2668 + 1)所以k = 1, x = (2668+1)/17 = 157当然，当k = 1 + 17n 时，x = (2668 + 17·n·2668 + 1)/17 = 157 + 2668n也符合条件（n任意整数）但如果限定2668 > x > 0，x是唯一的。

2008-03-20 20:13:27]字号：大while(scanf("%d%d",&d,&f)==2){printf("Enclid : gcd(%d,%d)=%d\n",d,f,Enclid(d,f));res=ExtEnclid(d,f);if(res==0) printf("Not Exist the d^-1\n");elseif(res>0) printf("ExtenderEnclid : d^-1 = %d , %d * %d = 1 mod %d\n",res,d,res,f);else{printf("ExtenderEnclid : d^-1 = (%d) ,%d * (%d) = 1 mod %d\n",res,d,res,f); printf("ExtenderEnclid : d^-1 = %d , %d * %d = 1 mod %d\n",res+f,d,res+f,f);}}return 0;}用扩展的欧几里德算法简单描述如下：ExtendedEuclid(d,f)1 （X1,X2,X3):=(1,0,f)2 (Y1,Y2,Y3):=(0,1,d)3 if (Y3=0) then return d'=null//无逆元4 if (Y3=1) then return d'=Y2 //Y2为逆元5 Q:=X3 div Y36 (T1,T2,T3):=(X1-Q*Y1,X2-Q*Y2,X3-Q*Y3)7 （X1,X2,X3):=(Y1,Y2,Y3)8 (Y1,Y2,Y3):=(T1,T2,T3)9 goto 3例1：（2/5) mod 17=2×5^-1 mod 17 (中间的是5的-1次方)=2×7 mod 17。

拓展的欧几里得算法求乘法逆元拓展的欧几里得算法又叫扩展欧几里得算法，是一种求解一元线性同余方程的方法，可以用来求解乘法逆元。

假设要求a在模n下的乘法逆元，即找到x满足ax ≡ 1 (mod n)。

算法步骤如下：1. 用欧几里得算法求出a和n的最大公约数gcd(a,n)以及对应的系数s和t。

2. 如果gcd(a,n)不等于1，则a在模n下没有乘法逆元。

3. 如果gcd(a,n)等于1，则ax ≡ 1 (mod n)可以转化为ax + ny = 1的形式，其中y为x的系数。

4. 用扩展的欧几里得算法求出gcd(a,n)的系数s和t，使得sa + tn = gcd(a,n)。

5. 把等式ax + ny = 1中的a用sa + tn替换，得到(sx +n'y)a + (ty) n = 1，其中n'为n的系数。

6. 取模得到(sx + n'y)a ≡ 1 (mod n)，即ax在模n下的乘法逆元为sx + n'y。

举例说明：计算16在模21下的乘法逆元。

1. 计算gcd(16,21)：21 = 1 × 16 + 5，16 = 3 × 5 + 1，gcd(16,21) = 1。

2. gcd(16,21) = 1，继续下一步。

3. 转化为16x + 21y = 1的形式，求出y的系数。

4. 用扩展的欧几里得算法求出gcd(16,21)的系数s和t，使得16s + 21t = gcd(16,21)，得到s = 11，t = -8。

5. 代入得到(11x - 8y)16 + 21y = 1，即(11x - 8y)16 ≡ 1 (mod 21)。

6. 求解得到x = 11，即16在模21下的乘法逆元为11。

注意事项：1. 模数n必须是正整数，且与a互质，否则a在模n下没有乘法逆元。

2. 扩展的欧几里得算法有多组解，根据具体问题设置取值范围。

扩展欧几里得算法求多项式逆元扩展欧几里得算法是一种用于求解线性方程ax+by=gcd(a,b)的算法，其中a和b是两个整数。

它的基本思想是利用辗转相除求解gcd，同时计算出使等式成立的x和y。

在这篇文章中，我们将介绍如何使用扩展欧几里得算法求多项式的逆元。

首先，让我们明确逆元的概念。

在数论中，如果a和b是整数，且满足(a*b)%m=1，那么我们称b是a模m的逆元。

在这里，%表示取模运算，即取除法的余数。

对于多项式而言，我们将多项式系数中的每个数都视为整数，因此我们可以将逆元的定义拓展到多项式上。

现在，让我们考虑一个多项式f(x)和一个模m。

我们想要求解一个多项式g(x)，使得(f(x)*g(x))%m=1。

换句话说，我们想要找到一个多项式g(x)，使得多项式乘法在模m意义下等于1。

这样的多项式g(x)被称为f(x)的逆元。

下面，我们将介绍如何使用扩展欧几里得算法来求解多项式的逆元。

算法步骤如下：1.首先，我们将需要求逆元的多项式f(x)表示为f(x)=a*x^n+b*x^(n-1)+...+c*x+d，其中a, b, ..., c, d是多项式系数，n是多项式的次数。

2.我们需要找到除法运算在模m意义下的逆元，即找到一个整数e，使得(e*m)%n=1。

这可以通过扩展欧几里得算法来实现。

我们可以将a和m作为输入参数，算法输出e和gcd(a,m)。

根据扩展欧几里得算法的特性，e和gcd(a,m)满足等式a*e+m*x=gcd(a,m)，其中x是一个整数。

3.然后，我们对多项式f(x)的每个系数应用步骤2中求得的逆元e。

即对于多项式系数a, b, ..., c, d，我们将其分别与e相乘，得到e*a, e*b, ..., e*c, e*d。

记多项式g(x)的系数为g0, g1, ..., gn，那么g0=e*d, g1=e*c, ..., gn=e*a。

4.最后，我们将多项式g(x)的系数对模m进行取模运算。

模逆运算快速算法——扩展的Euclid 算法与扩展的Stein 算法(1)扩展的Euclid 算法求模逆的传统算法是扩展的Euclid 算法，该算法是在用Euclid 算法求取二个数的最大公因子时，若最大公因子为1，说明二个数互素，则可同时得出二者的乘法逆元。

算法描述如下：输入：二个整数a 、b ，设b a >输出：a 与b 的最大公因子；若二者互素，同时得出乘法逆元Step 1: ),0,1(),,(321a X X X ←，),1,0(),,(321N Y Y Y ← Step 2: if 03=Y then return ),gcd(3b a X =，no inverseStep 3: if 13=Y then return ),gcd(3b a Y =，a Y b m od 21=-，b b Y a m od )(11+=-Step 4: ⎣⎦33Y X Q =Step 5: ),,(),,(332211321QY X QY X QY X T T T ---← Step 6: ),,(),,(321321Y Y Y X X X ← Step 7: ),,(),,(321321T T T Y Y Y ←Step 8: goto Step 2 (2)扩展的Stein 算法较之扩展的Euclid 算法，扩展的Stein 算法可以得到更高的执行效率。

Stein 算法基于以下求取二个数公因子的基本性质： 1)若a 与b 都是偶数，则)2,2gcd(2),gcd(b a b a = 2)若a 为偶数、b 为奇数，则),2gcd(),gcd(b a b a = 3)若a 与b 都是奇数，则),2)(gcd(),gcd(b b a b a -=由于除2在二进制运算中仅做一次移位操作，因此可以说Stein 算法主要只用到了减法，通过计算复杂性分析可知，在最坏情况下，Stein 算法所需减法次数为)13()(-+lb a lb 。