欧几里得算法

欧几里得算法（又称 辗转相除法），通常用于计算两个正整数的最大公约数。

通过辗转相除的方法求两数的最大公约数。

计算方法 :

1、先比较两数的大小，用 大的数 取余 小的数

2、把 小的数的值 给 大的数，将取余的结果 给 小的数

3、重复 步骤2 直到小的数为0（或 大的数 能整除 小的数 ）

取得的最后一个非 0 余数即为 两数的最大公约数

例如：

a = 12 ；b = 78

a 和 b 的最大公约数可以通过欧几里得算法这样计算 ：

首先比较 a 与 b 的大小，若 a 小于 b 则交换 a 、b 的值，---> a = 78 ； b = 12 。

temp = b ; b = a%b ; a = temp ---> a = 12 ; b = 78 % 12 = 6 。（这里使用中间变量 temp 存储 原来b的值 ）

temp = b ; b = a%b ; a = temp ---> a = 6 ; b = 12 % 6 = 0 。（这里得到 b = 0 了，即计算出了最大公约数是 6）

得出 a = 12 和 b =78 的最大公约数 为 6 。

验算：

a = 12 = 2 2 3

b = 78 = 2 3 13

a 与 b 最大公约数 为 2 * 3 = 6 。计算结果正确。

扩展欧几里得算法

扩展欧几里得算法是欧几里得算法的扩展版本，
不仅能计算两个整数的最大公约数 gcd(a,b)，
还能找到满足贝祖等式 a*x + b*y = gcd(a,b) 的整数系数 x 和 y 。
形如：
99*14 + 78*-11 = 3   
9291*1260 + 789*-107 = 3
9295*-405 + 7895*344 = 5

系数x是a的逆元，b的系数y是b的逆元

扩展欧几里得算法，常用于在 RSA 解密 中求 私钥d（ 即逆元 ）。

扩展欧几里得算法用于实现

已知 a * x ≡ c ( mod n ) ，使得有 x 和 y 满足贝祖等式的 x * a + y * n = gcd( a , n ) ，求出 系数 x 和 y 以及 gcd(a,n) 的值。

计算步骤：

1、初始化 x 和 y 的值 为 x0 =1 和 y0 = 0 。

2、当前值 x1 = 0 、y1 = 1 、a (当前已知) 、b (当前已知) 、q ( 开始计算时首个计算，q = a // b ) 、temp ( 中间变量 )。

3、计算：

  • q = a // b
  • xn+1 = xn-1 - xn * q
  • yn+1 = yn-1 - yn * q
  • temp = b ; b = a % b ; a = temp ( 或者写成 a , b = b , a % b 的形式 ，不使用中间变量 )

4、重复计算 步骤3 ，直到 b = 0 ( 即 找到 a 与 b 的最大公约数 gcd ( a , n )) 为止 。

5、得出最终结果的 x = xend-1 、 y = yend-1 、gcd ( a , n ) = a 。

计算得出的 系数 x 即为 a 模 n 同余 c 的逆元

例如：

在RSA加解密中，已知

密文 c = 23871287369518024966670244554752020008236499719904025287161261775504783383672679833751945810736664297968279268387488641635606313123351760756157577396387782179147485616702073959008697988421576869258642082256186075000011966442082327338681191576737151863834201625669929141282079483890794699041419707079818356412、

公钥 e = 65537 、

p = 11236929864875682553741625226004507304079573558740811780926590694034552060951903651847796054450872512431987649566055560082139627311889945917928338348777881、

q = 6827614655534636407294283206896465716248674687764964214639358338539080212705206514758091712027779129452928520656531368752268160864176528797868256461667597，

求出私钥 d 和密文 m 的值。（常规的RSA加解密中采用的p和q多为1024、2048及更大的位数，我这里采用的是512位）

解：在RSA加密中 c = me mod n ，而解密需要知道 e关于 ϕ(n) = ( p - 1 ) * ( q - 1 ) 的逆元 即私钥 d ，而求私钥 d 则可以使用扩展欧几里得算法 求 e 模 ϕ(n) 的逆元。

由 p 和 q 可以求出 ϕ(n) = ( p - 1 ) * ( q - 1 ) = 76721427028640051769029115655097353115665105270940166910722414255224330082789660228284430155655346068635222608100935927179510013581266870566293767573881949227988665710539377048226289712359486286022938305689026296835894639750462151651953684952444691825008577701366184878061914244897381417956112732173397576480 。

然后通过 e 和 ϕ(n) 使用扩展欧几里得算法算出 e 的逆元 d = -2646858210045549186715516891163390380922514045769499937213228842196960653023290992510354404106638043565989262812094177813340130624032903464461147267719716911126270246906778331416446298116251865247079718466864343151898283114512335396570903179539457836280946552066602743630285000956909522651307976981614231967 ，由于当前的 d 是负数 ，所以需要对 d 取余 ϕ(n)，然后得到 d = 74074568818594502582313598763933962734742591225170666973509185413027369429766369235774075751548708025069233345288841749366169882957233967101832620306162232316862395463632598716809843414243234420775858587222161953683996356635949816255382781772905233988727631149299582134431629243940471895304804755191783344513 。

最后通过 cd mod n = m 计算出 明文 m = 2306163833538300270279074959817587972266681700 。

验算：直接将计算出的 m 加密成 c ，看是否与题中的 c 相等。

me mod n = 23871287369518024966670244554752020008236499719904025287161261775504783383672679833751945810736664297968279268387488641635606313123351760756157577396387782179147485616702073959008697988421576869258642082256186075000011966442082327338681191576737151863834201625669929141282079483890794699041419707079818356412 与题中所给的 c 相同 ，所以计算正确。

附上Python代码实现

# 欧几里得算法
def gcd(a,b):
    # 判断a与b的大小关系，其实这一步可以省略
    if a<b:
        a,b=b,a
    # 计算a，b的最大公约数并返回
    while a%b:
        a,b=b,a%b
    return b

# 扩展欧几里得算法
def extended_gcd1(a,b):
    if a%b!=0:  # 如果a与b不是整除关系，则继续进行运算，否则无法得出逆元
        # 正负号处理
        sign_a, a = (-1, -a) if a < 0 else (1, a)
        sign_b, b = (-1, -b) if b < 0 else (1, b)
        # 初始化
        old_s,s=1,0
        old_t,t=0,1
        # print('{:<20}{:<20}{:<20}{:<20}{:<20}{:<20}{:<20}'.format('a', 'b', 'old_s', 's', 'old_t', 't','q'))
        # print('{:<20}{:<20}{:<20}{:<20}{:<20}{:<20}{:<20}'.format(a, b, old_s, s, old_t, t, '-'))
        while b!=0:
            q=a//b
            old_s,s=s,old_s-s*q
            old_t,t=t,old_t-t*q
            a,b=b,a%b
            # print('{:<20}{:<20}{:<20}{:<20}{:<20}{:<20}{:<20}'.format(a, b, old_s, s, old_t, t,q))
        return (a,old_s*sign_a,old_t*sign_b)
    return None