密碼學基礎-擴充的歐幾裡得算法求乘法逆元

一、先了解幾個定義

規定定義在正整數上的二進制函數gcd(a, b)(a≥b)表示正整數a和正整數b的最大公約數，例如：gcd(6,3)=3, gcd(7,4)=1.運算mod表示模數運算，例如5 mod 3 = 2, 或者 5 = 2 (mod 3)

歐幾裡德有個十分又用的定理： gcd(a, b) = gcd(b , a%b) ，這樣，我們就可以在幾乎是 log 的時間複雜度裡求解出來 a 和 b 的最大公約數了，這就是歐幾裡德算法。例如：gcd(15750, 27216) = gcd(15750, 11466)=gcd(11466,4284)=gcd(4284, 2898) = gcd(2898, 1386) = gcd(1386, 126) = gcd(126, 0) = 126

二、擴充的歐幾裡得算法

給出正整數a和b，擴充的歐幾裡得算法可以計算a和b的最大公約數d，同時得到兩個符号相反的整數x和y滿足：d=gcd(a, b) = ax+by

乘法逆元

簡單說，如果有：ab mod q = 1成立，則稱a和b互為模q意義下的乘法逆元（a與b均與q互質）。

二、根據擴充的歐幾裡得算法求乘法逆

若a與b互質，那麼d=gcd(a, b)=1, 即 ax + by = 1, 于是 by = (-x)a+1

也即：by=1(mod a)，于是y即為b在模a意義下的乘法逆元。

在歐幾裡得算法中，可以把過程寫的更清晰一些：

（仍以d=gcd(a,b)=ax+by為例）

a = q1b + r1, r1=ax1+by1;

b = q2r1 + r2, r2=ax2+by2;

r1 = q3r2 + r3, r3=ax3+by3;

… … … …

r(n-2) = q(n)r(n-1)+r(n), r(n)=ax(n)+b*y(n)

r(n-1) = q(n+1)*r(n)+0

則：r(i-2) = q(i)r(i-1)+r(i)或 r(i) = r(i-2) - r(i-1)q(i)

又r(i-1) = ax(i-1)+by(i-1)且r(i-2) = ax(i-2)+by(i-2)

帶入得：

x(i) = x(i-2)-q*x(i-2)

y(i) = y(i-2)-q*y(i-2)

于是，據此可以建構一個表格來計算乘法逆元，可以在草稿紙上快速手算的那種，在考試中很有用，程式設計方法其它博文一般都有講，就不提了

計算	滿足	計算	滿足
r(-1)=a	x(-1)=1; y(-1)=0	a = ax(-1)+by(-1)
r(0)=b	x(0)=0; y(0)=1	b = ax(0)+by(0)
r(1)=a mod b q(1)=a/b	r(-1)=q(1)*r(0)+r(1)	x(1) = x(-1)-q(1)*x(0) y(1) = y(-1)-q(1)*y(0)	r(1)=ax(1)+by(1)
…	…	…	…
r(n)=r(n-2) mod r(n-1), q(n)=r(n-2)/r(n-1)	r(n-2)=q(1)*r(n-1)+r(n)	x(n) = x(n-2)-q(n)*x(n-1) y(n) = y(n-2)-q(n)*y(n-1)	r(n)=ax(n)+by(n)
r(n+1) = r(n-1) mod r(n)=0 , q(n+1)=r(n-1)/r(n)	r(n-1)=q*r(n)+0	d=gcd(a,b)=r(n), x=x(n) , y=y(n)

注：表格中的除法都是整除

下面舉一個例子，令a=1759, b=550,求x和y使得

ax+by=gcd(a,b)

i	ri	qi	xi	yi
-1	1759	1
550	1
1	109	3	1	-3
2	5	5	-5	16
3	4	21	106	-339
4	1	1	-111	355
5	4

解釋：以i=2這一列為例：

r2 = r1 mod r0 = 550 mod 109 = 5; q2=550/109=5;

x2 = x0-q2*x1 = 0-5*1=-5; y2 = 1-5*(-3)=16

由此，1759*(-111)+550355 = 1

550×355 = 111×1759 + 1

550×355 = 1（mod 1759）

題目：求550在模1759下的乘法逆元。

答：乘法逆元是355

另，還可以這樣看：

1759(-111) = (-355)*550+1

1759×（-111）= 1（mod 550)

題目：求1759在模550下的乘法逆元。

答：乘法逆元是-111+550=439

再看一個例子，求7的乘法逆元(mod 71)

先建表，得算式1×71+(-10)×7 = 1，

故而7關于71的乘法逆元是-10+71 = 61.

讀者可自行驗算之

好了，歐幾裡德算法筆算方法先介紹到這裡，以後補充其它方法。