2016/02/01

RSA算法(2) 欧几里得算法


Euclid ,中文译作“欧几里得”,古希腊数学家。他用公理化系统的方法归纳整理了当时的几何理论,并写成了伟大的数学著作《几何原本》,因而被后人称作“几何学之父”。有趣的是, 《几何原本》一书里并不全讲的几何。全书共有十三卷,第七卷到第十卷所讨论的实际上是数论问题——只不过是以几何的方式来描述的。在《几何原本》中,数的大小用线段的长度来表示,越长的 线段就表示越大的数。很多数字与数字之间的简单关系,在《几何原本》中都有对应的几何语言。例如,若数字 a 是数字 b 的整倍数,在《几何原本》中就表达为,长度为 a 的线段可以用长度为 b 的线段来度量。 比方说,黑板的长度是 2.7 米,一支铅笔的长度是 18 厘米,你会发现黑板的长度正好等于 15 个铅笔的长度。我们就说,铅笔的长度可以用来度量黑板的长度。如果一张课桌的长度是 117 厘米, 那么 6 个铅笔的长度不够课桌长, 7 个铅笔的长度又超过了课桌长,因而我们就无法用铅笔来度量课桌的长度了。哦,当然,实际上课桌长相当于 6.5 个铅笔长,但是铅笔上又没有刻度,我们用 铅笔来度量课桌时,怎么知道最终结果是 6.5 个铅笔长呢?因而,只有 a 恰好是 b 的整数倍时,我们才说 b 可以度量 a

给定两条长度不同的线段 a 和 b ,如果能够找到第三条线段 c ,它既可以度量 a ,又可以度量 b ,我们就说 a 和 b 是可公度的( commensurable ,也叫做可通约的)c 就是 a 和 b 的一个公度单位。 举个例子: 1 英寸和 1 厘米是可公度的吗?历史上,英寸和厘米的换算关系不断在变,但现在,英寸已经有了一个明确的定义: 1 英寸精确地等于 2.54 厘米。因此,我们可以把 0.2 毫米当作单位长度, 它就可以同时用于度量 1 英寸和 1 厘米: 1 英寸将正好等于 127 个单位长度, 1 厘米将正好等于 50 个单位长度。实际上, 0.1 毫米、 0.04 毫米 、 (0.2 / 3) 毫米也都可以用作 1 英寸 和 1 厘米的公度单位,不过 0.2 毫米是最大的公度单位。

等等,我们怎么知道 0.2 毫米是最大的公度单位?更一般地,任意给定两条线段后,我们怎么求出这两条线段的最大公度单位呢?在《几何原本》第七卷的命题 2 当中, Euclid 给出了一种求 最大公度单位的通用算法,这就是后来所说的 Euclid 算法。这种方法其实非常直观。假如我们要求线段 a 和线段 b 的最大公度单位,不妨假设 a 比 b 更长。如果 b 正好能度量 a ,那么考 虑到 b 当然也能度量它自身,因而 b 就是 a 和 b 的一个公度单位;如果 b 不能度量 a ,这说明 a 的长度等于 b 的某个整倍数,再加上一个零头。我们不妨把这个零头的长度记作 c 。 如果有某条线段能够同时度量 b 和 c ,那么它显然也就能度量 a 。也就是说,为了找到 a 和 b 的公度单位,我们只需要去寻找 b 和 c 的公度单位即可。怎样找呢?我们故技重施,看看 c 是 否能正好度量 b 。如果 c 正好能度量 b ,c 就是 b 和 c 的公度单位,从而也就是 a 和 b 的公度单位;如果 c 不能度量 b ,那看一看 b 被 c 度量之后剩余的零头,把它记作 d ,然后 继续用 d 度量 c ,并不断这样继续下去,直到某一步没有零头了为止。

/blog/img/rsa2_01.png

我们还是来看一个实际的例子吧。让我们试着找出 690 和 2202 的公度单位。显然, 1 是它们的一个公度单位, 2 也是它们的一个公度单位。我们希望用 Euclid 的算法求出它们的最大公度单位。 首先,用 690 去度量 2202 ,结果发现 3 个 690 等于 2070 ,度量 2202 时会有一个大小为 132 的零头。接下来,我们用 132 去度量 690 ,这将会产生一个 690 – 132 × 5 = 30 的零头。 用 30 去度量 132 ,仍然会有一个大小为 132 – 30 × 4 = 12 零头。再用 12 去度量 30 ,零头为 30 – 12 × 2 = 6 。最后,我们用 6 去度量 12 ,你会发现这回终于没有零头了。 因此, 6 就是 6 和 12 的一个公度单位,从而是 12 和 30 的公度单位,从而是 30 和 132 的公度单位,从而是 132 和 690 的公度单位,从而是 690 和 2202 的公度单位。

我们不妨把 Euclid 算法对 a 和 b 进行这番折腾后得到的结果记作 x 。从上面的描述中我们看出, x 确实是 a 和 b 的公度单位。不过,它为什么一定是最大的公度单位呢?为了说明这一点, 下面我们来证明,事实上, a 和 b 的任意一个公度单位一定能够度量 x ,从而不会超过 x 。如果某条长为 y 的线段能同时度量 a 和 b ,那么注意到,它能度量 b 就意味着它能度量 b 的任意整倍数, 要想让它也能度量 a 的话,只须而且必须让它能够度量 c 。于是, y 也就能够同时度量 b 和 c ,根据同样的道理,这又可以推出 y 一定能度量 d ……因此,最后你会发现, y 一定能度量 x 。

用现在的话来讲,求两条线段的最大公度单位,实际上就是求两个数的最大公约数——最大的能同时整除这两个数的数。用现在的话来描述 Euclid 算法也会简明得多:假设刚开始的两个数是 a 和 b , 其中 a > b ,那么把 a 除以 b 的余数记作 c ,把 b 除以 c 的余数记作 d ,c 除以 d 余 e , d 除以 e 余 f ,等等等等,不断拿上一步的除数去除以上一步的余数。直到某一次除法余数 为 0 了,那么此时的除数就是最终结果。因此, Euclid 算法又有一个形象的名字,叫做“辗转相除法”。写一个C程序来描述下非常简单

//原理: gcd(a,b)=gcd(b,a mod b)
//当b为0时,两数的最大公约数即为a
int
Gcd(int M,int N) {
    int Rem;
    while(N > 0) {
        Rem = M % N;
        M = N;
        N = Rem;
    }
    return M;
}

辗转相除法的效率非常高,刚才大家已经看到了,计算 690 和 2202 的最大公约数时,我们依次得到的余数是 132, 30, 12, 6 ,做第 5 次除法时就除尽了。实际上,我们可以大致估计出辗 转相除法的效率。第一次做除法时,我们是用 a 来除以 b ,把余数记作 c 。如果 b 的值不超过 a 的一半,那么 c 更不会超过 a 的一半(因为余数小于除数);如果 b 的值超过了 a 的一半, 那么显然 c 直接就等于 a – b ,同样小于 a 的一半。因此,不管怎样, c 都会小于 a 的一半。下一步轮到 b 除以 c ,根据同样的道理,所得的余数 d 会小于 b 的一半。接下来, e 将小 于 c 的一半, f 将小于 d 的一半,等等等等。按照这种速度递减下去的话,即使最开始的数是上百位的大数,不到 1000 次除法就会变成一位数(如果算法没有提前结束的话),交给计算机来 执行的话保证秒杀。用专业的说法就是,辗转相除法的运算次数是对数级别的

很长一段时间里,古希腊人都认为,任意两条线段都是可以公度的,我们只需要做一遍辗转相除便能把这个公度单位给找出来。事实真的如此吗?辗转相除法有可能失效吗?我们至少能想到一种可 能:会不会有两条长度关系非常特殊的线段,让辗转相除永远达不到终止的条件,从而根本不能算出一个“最终结果”?注意,线段的长度不一定(也几乎不可能)恰好是整数或者有限小数,它们往往 是一些根本不能用有限的方式精确表示出来的数。考虑到这一点,两条线段不可公度完全是有可能的。

为了让两条线段辗转相除永远除不尽,我们有一种绝妙的构造思路:让线段 a 和 b 的比值恰好等于线段 b 和 c 的比值。这样,辗转相除一次后,两数的关系又回到了起点。今后每一次辗转相除, 余数总会占据除数的某个相同的比例,于是永远不会出现除尽的情况。不妨假设一种最为简单的情况,即 a 最多只能包含一个 b 的长度,此时 c 等于 a – b 。解方程 a / b = b / (a – b) 可以 得到 a : b = 1 : (√5 – 1) / 2 ,约等于一个大家非常熟悉的比值 1: 0.618 。于是我们马上得出:成黄金比例的两条线段是不可公度的

/blog/img/rsa2_02.png

更典型的例子则是,正方形的边长和对角线是不可公度的。让我们画个图来说明这一点。如图,我们试着用辗转相除求出边长 AB 和对角线 AC 的最大公度单位。按照规则,第一步我们应该用 AB 去度量 AC , 假设所得的零头是 EC 。下一步,我们应该用 EC 去度量 AB ,或者说用 EC 去度量 BC (反正正方形各边都相等)。让我们以 EC 为边作一个小正方形 CEFG ,容易看出 F 点将正好落在 BC 上, 同时三角形 AEF 和三角形 ABF 将会由于 HL 全等。因此, EC = EF = BF 。注意到 BC 上已经有一段 BF 和 EC 是相等的了,因而我们用 EC 去度量 BC 所剩的零头,也就相当于用 EC 去 度量 FC 所剩的零头。结果又回到了最初的局面——寻找正方形的边长和对角线的公度单位。因而,辗转相除永远不会结束。线段 AB 的长度和线段 AC 的长度不能公度,它们处于两个不同的世界中。


本文出自:http://www.matrix67.com/blog/archives/5100