RSA原理：欧几里德算法与奥数内容辗转相除法——挑战PythonTip

2017-12-17T23:00:00+08:00

PythonTip 里未攻克的题目，如RSA密码方程，如今积累工作经验之后从新挑战，仍然失败未成功了。把过程记录分享下。

描述:¶

在RSA密码体系中,欧几里得算法是加密或解密运算的重要组成部分。它的基本运算过程就是解 (x*a) % n = 1 这种方程。其中，x,a,n皆为正整数。现在给你a和n的值(1 < a,n < 140000000)，请你求出最小的满足方程的正整数解x（保证有解）. 如：a = 1001, n = 3837，则输出23。

分析：¶

没头绪，在讨论里看时恍然，用到小学奥术内容辗转相除法（求最大公约数）了。如果 (x*a) % n = 1 变成 (x*a) % n = 0 ，那x*a就是a和n公倍数了。如果这是小学奥数题，就先用辗转相除法得最大公约数，而最小公倍数用两数积除以最大公约数得出来。 rsa的原理数学基础欧几里得算法和小学奥数有着这样的联系，发现这点让我觉得不可思议又略有惊叹。看来学小学奥数有用，至少是可以为算法编程做准备的，学到了最朴素的数论。

辗转相除法（朴素欧几里得算法，中国余数定理，韩信点兵）¶

（引用自数论——欧几里得算法）

欧几里得算法，又名辗转相除法，是求最大公约数的算法。两个整数的最大公约数是能够同时整除它们的最大的正整数。辗转相除法基于如下原理：两个整数的最大公约数等于其中较小的数和两数的差的最大公约数。例如，252和105的最大公约数是21（252 = 21 × 12；105 = 21 × 5）；因为252 − 105 = 147，所以147和105的最大公约数也是21。在这个过程中，较大的数缩小了，所以继续进行同样的计算可以不断缩小这两个数直至其中一个变成零。这时，所剩下的还没有变成零的数就是两数的最大公约数。

题目语义转化¶

求这样一个数x*a，能被a整除，被n整除余1。

这就很形似 有一个数除以3余2，除以5余3，除以7余4，除以9余5．这个数至少是? 被称为中国余数定理

扩展欧几里德算法¶

基本算法：对于不完全为 0 的非负整数 a，b，gcd（a，b）表示 a，b 的最大公约数，必然存在整数对 x，y ，使得 gcd（a，b）=ax+by。

证明：设 a>b。

1，显然当 b=0，gcd（a，b）=a。此时 x=1，y=0；

2，ab!=0 时

设 ax1+by1=gcd(a,b);

bx2+(a mod b)y2=gcd(b,a mod b);

根据朴素的欧几里德原理有 gcd(a,b)=gcd(b,a mod b);

则:ax1+by1=bx2+(a mod b)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.

上面的思想是以递归定义的，因为 gcd 不断的递归求解一定会有个时候 b=0，所以递归可以结束。

…

同余方程 ax≡b (mod n)对于未知数 x 有解，当且仅当 gcd(a,n) | b。且方程有解时，方程有 gcd(a,n) 个解。

求解方程 ax≡b (mod n) 相当于求解方程 ax+ ny= b, (x, y为整数)

我的一个另类编程解法（融合了辗转相除法思想）。¶

算法描述¶

(x*a) % n = 1 对应方程 ax - ny = 1 的整数解

（a,n必定互质。如不互质可提取公因子，公因子*X=1，与X为整数矛盾）

化简降解方程分两情况：

a>=n 时变形为方程 (a mod n)x - n(y-[a/n]x) = 1 有整数解
a<n 时变形为方程 a(x-[n/a]a) - (n mod a)y = 1 有整数解

无论那一种都变回 ax - ny = 1 的形式。所以重复化简，因a,n互质，最后会到达a,n其一是1的情况。

例子说明：求能被9整除，被7除余1的最小数¶

9x=1(mod7) 对应方程 9x - 7y = 1 的整数解
变形有2x - 7(y-x) = 1 然后令 x_1=x, y_1=y-x 得方程 2x_1 - 7y_1 = 1
变形有2(x_1-3y_1) - y_1 = 1 然后令 x_2=x_1-3y_1, y_2=y_1 得方程 2x_2 - y_2 = 1 显然有解 x_2=1 y_2=1
好了，往上一步一步回溯得最初的x,y值 (x_2,y_2), (x_1,y_1), (x,y) 分别为(1,1),(4,1),(4,5)
9x = (94 mod 97) = 36 答：求能被9整除，被7除余1的数是36

python语言是弱递归化语言， python之父说递归都可以转成循环。所以我用递归后，转循环了。

Python代码:¶

################################################################################
# print "F: 答案错误 循环解法"
################################################################################
def gcd(a,n): # 辗转相除求最大公约数
    if a < n: a,n = n,a
    while n != 0: a,n = n,a%n
    return a

def exgcd(a, n): # ax=1(mod n) 即 ax-ny=1 求x,y     
    # print a,n
    if gcd(a,n) != 1:   raise Exception('fei hu zhi') # 先检查是否互质
    l = []
    while a!=1 and n!=1: # a,n总会有个先到1，触底条件就是1
        l.append((a,n))
        if a>n: a,n = a%n,n
        else:   a,n = a,n%a
    if a==1:    p = (n+1, 1)
    elif n==1:  p = (1, a-1)

    for a,n in l[::-1]:
        if a>n: p = (p[0] % n, (a//n*p[0]+p[1]) % a) # 这个值也是解，但没有最简：return (p[0], a//n*p[0]+p[1])
        else:   p = ((p[0]+n//a*p[1]) % n, p[1] % a) # 这个值也是解，但没有最简：return (p[0]+n//a*p[1], p[1])
    return p

print exgcd(a,n)

################################################################################
# print "F: 答案错误 递归解法"
################################################################################
def gcd_r(a,n): # 辗转相除求最大公约数
    if a * n == 0: return a+n
    return gcd_r(a%n,n) if a>=n else gcd_r(a,n%a)
# print gcd(a,n)

def exgcd_r(a, n): # ax=1(mod n) 即 ax-ny=1 求x,y     # a,n总会有个先到1，触底条件就是1
    # print a,n
    if gcd_r(a,n) != 1:   raise Exception('fei hu zhi') # 先检查是否互质
    if a==1: return (n+1, 1)
    if n==1: return (1, a-1)
    if a>n:     
        p = exgcd_r(a%n, n)
        return (p[0] % n, (a//n*p[0]+p[1]) % a) # 这个值也是解，但没有最简：return (p[0], a//n*p[0]+p[1])
    else:
        p = exgcd_r(a, n%a) 
        return ((p[0]+n//a*p[1]) % n, p[1] % a) # 这个值也是解，但没有最简：return (p[0]+n//a*p[1], p[1])

print exgcd_r(a,n)

小学初中就知道数论，数论真有魅力，非常漂亮。

参考¶

数论——欧几里得算法 https://xuanwo.org/2015/03/11/number-theory-gcd/

欧几里德与扩展欧几里德算法 http://www.cnblogs.com/frog112111/archive/2012/08/19/2646012.html

欧几里得算法（辗转相除法） https://my.oschina.net/u/1780798/blog/646739

https://zhidao.baidu.com/question/406531667.html?qbl=relate_question_3

Linux迷+Python粉 - 奥数