密码学基础

辗转相除法， 又名欧几里德算法（Euclidean algorithm），是求最大公约数的一种方法。它的具体做法是：用较小数除较大数，再用出现的余数（第一余数）去除除数，再用出现的余数（第二余数）去除第一余数，如此反复，直到最后余数是0为止。如果是求两个数的最大公约数，那么最后的除数就是这两个数的最大公约数。

另一种求两数的最大公约数的方法是更相减损法。

中文名

辗转相除法

外文名

Euclidean algorithm

别    称

欧几里德算法

用    途

求最大公约数

编辑

两个数的最大公约数是指能同时整除它们的最大正整数。

设两数为a、b(a≥b)，求a和b最大公约数  的步骤如下：

(1)用a除以b(a≥b)，得  。

(2)若  ，则  ；

(3)若  ，则再用b除以  ，得  .

(4)若  ，则  ；若  ，则继续用  除以  ，......，如此下去，直到能整除为止。其最后一个余数为0的除数即为  的最大公约数。

编辑

设两数为a、b(a>b)，用  表示a，b的最大公约数，r=a (mod b) 为a除以b的余数，k为a除以b的商，即  。辗转相除法即是要证明  。

第一步：令  ，则设 

第二步：根据前提可知 

第三步：根据第二步结果可知，  也是  的因数

第四步：可以断定  与  互质（这里用反证法进行证明：设  ，则  ，则  ，则a与b的一个公约数  ，故c非a与b的最大公约数，与前面结论矛盾，因此c也是b与r的最大公约数）从而可知  ，继而  。

证毕

注：以上步骤的操作是建立在刚开始时  的基础之上的，即m与n亦互质。 [1] 

编辑

用辗转相除法确定两个正整数 a 和 b(a≥b) 的最大公因数  当  时，  ；否则  递归或循环运算得出结果。

算法流程图如下：

伪代码描述如下：

1

2

3

4

5

6

7

function gcd(a,b) 

{

if b0

        return gcd(b,a mod b);

else

        return a；

}

编辑

123456 和 7890 的最大公因数是 6，这可由下列步骤（其中，“a mod b”是指取 a ÷ b 的余数）看出：

a

b

a mod b

123456

7890

5106

7890

5106

2784

5106

2784

2322

2784

2322

462

2322

462

12

462

12

6

12

6

0

已知不定方程为

，利用辗转相除法求出一组整数解 

解：求  的算式为：

所以

即

所以

所以

是不定方程

的一组解。

1

2

3

4

5

6

7

int GCD(int a,int b)

{

return b==0?a:GCD(b,a%b);

}

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

public static int gcd(int m, int n) 

{

while (true) 

    {

if ((m = m % n) == 0)

return n;

if ((n = n % m) == 0)

return m;

}

}

费马小定理是数论中的一个定理：假如是一个整数，是一个质数，那么是p的倍数，可以表示为，如果a不是p的倍数，这个定理也可以写成，

这个书写方式更加常用。

费马小定理是欧拉定理的一个特殊情况：如果n和a的最大公因数是1，那么

这里φ(n)是欧拉函数。欧拉函数的值是所有小于或等于n的正整数中与n互质的数的个数。假如n是一个素数（质数），则φ(n) = n-1，即费马小定理。

欧拉函数

请思考以下问题：

　　任意给定正整数n，请问在小于等于n的正整数之中，有多少个与n构成互质关系？（比如，在1到8之中，有多少个数与8构成互质关系？）

计算这个值的方法就叫做欧拉函数，以φ(n)表示。在1到8之中，与8形成互质关系的是1、3、5、7，所以 φ(n) = 4。

φ(n) 的计算方法并不复杂，但是为了得到最后那个公式，需要一步步讨论。

第一种情况

如果n=1，则 φ(1) = 1 。因为1与任何数（包括自身）都构成互质关系。

第二种情况

如果n是质数，则 φ(n)=n-1 。因为质数与小于它的每一个数，都构成互质关系。比如5与1、2、3、4都构成互质关系。

第三种情况

如果n是质数的某一个次方，即 n = p^k (p为质数，k为大于等于1的整数)，则

比如 φ(8) = φ(2^3) =2^3 - 2^2 = 8 -4 = 4。

这是因为只有当一个数不包含质数p，才可能与n互质。而包含质数p的数一共有p^(k-1)个，即1×p、2×p、3×p、...、p^(k-1)×p，把它们去除，剩下的就是与n互质的数。

上面的式子还可以写成下面的形式：

可以看出，上面的第二种情况是 k=1 时的特例。

第四种情况

如果n可以分解成两个互质的整数之积，

　　n = p1 × p2

则

　　φ(n) = φ(p1p2) = φ(p1)φ(p2)

即积的欧拉函数等于各个因子的欧拉函数之积。比如，φ(56)=φ(8×7)=φ(8)×φ(7)=4×6=24。

这一条的证明要用到"中国剩余定理"，这里就不展开了，只简单说一下思路：如果a与p1互质(a