欧几里得算法

首先介绍计算最大公约数$(gcd)$的问题。两个正整数$r_0$和$r_1$的$gcd$表示为$$gcd(r_0,r_1)$$它指的是被$r_0$和$r_0$同时整除的最大正整数。例如$gcd(21，9)=3$。对小整数而言，$(gcd)$的计算非常容易，就是将两个整数因式分解，并找出最大的公共因子。

然而，对公钥方案中使用的大整数而言，因式分解通常是不可能的。所以，人们通常使用一种更有效的算法计算 $(gcd)$，那就是欧几里得算法。此算法基于一个简单的观察，即$$gcd(r_0,r_1)=gcd(r_0-r_1,r_1)$$其中，通常假设$r_0>r_1$，并且两个数均为正整数。

此属性的证明非常简单: 假设$gcd(r_0,r_1)=g$，由于$g$可以同时除$r_0$和$r_1$，则可以记作$r_0=g\cdot x$和$r_1=g\cdot y$，其中x > y,且x和y为互素的整数，即它们没有公共因子。此外，证明(x-y)与y互素也非常简单,这里可以使用反证法很容易证明(x-y)与y互素。因此可以得到:$$gcd(r_0,r_1)=gcd(r_0-r_1,r_1)=gcd(g.(x-y),g.y)=g$$

示例: 假设$r_0=84，r_1=30$，则$r_0-r_1$与$r_1$的gcd为:
$$r_0-r_1=84-30=54=2\ast 3\ast 3\ast 3$$ $$r_1=30=2\ast 3\ast 5$$
最大公因子仍然是：$2\cdot 3=6=gcd(30,54)=gcd(30,84)。$

只要满足$(r_0-m{r}_1)>0$，迭代地使用这个过程可以得到:$$gcd(r_0,r_1)=gcd(r_0-r_1,r_1)=gcd(r_0-2r_1,r_1)=\dots =gcd(r_0-m{r}_1,r_1)$$如果m选择了最大值，则此算法使用的步骤也是最少的。这种情况可以表示为:
$$gcd(r_0,r_1)=gcd(r_{0}mod{r}_1,r_1)$$由于第一项$(r_{0}mod{r}_1)$比第二项$r_1$小，通常可以交换它们:$$gcd(r_0,r_1)=gcd(r_1,r_{0}mod{r}_1)$$这个过程的核心关注点在于，我们可将查找两个给定整数的$gcd$简化为查找两个较小整数的$gcd$。迭代地进行这个过程，直到最后得到$gcd(r_l,0)=r_l$。由于每轮迭代都保留了前一轮迭代步骤的$gcd$，事实证明:最终的$gcd$就是原始问题的$gcd$，即:$$gcd(ro,r_1)=\dots =gcd(r_l,0)=r_l$$
示例: 假设$r_0=973，r_1=301$，则$gcd$为:

解：$gcd(973,301)=gcd(301,973mod301)=gcd(301,70)=gcd(70,301mod70)=gcd(70,21)=gcd(21,70mod21)=gcd(21,7)=gcd(7,21mod7)=gcd(7,0)=7$

Java实现欧几里得算法：

/**
 * @Author Mr.Lu
 * @Date 2022/6/25 16:11
 * @ClassName EuclideanAlgorithm
 * @Version 1.0
 */
public class EuclideanAlgorithmDemo {
    public static void main(String[] args) {
        System.out.println(euclideanAlgorithm(973, 301));
    }

    public static int euclideanAlgorithm(int r0, int r1){
        // 利用位运算，始终保持ro >= r1
        if(r1 >  r0){
            r0 =  r0 ^ r1;
            r1 =  r0 ^ r1;
            r0=  r0 ^ r1;
        }

        // 递归结束条件r1 == 0
        if(r1 == 0){
            return r0;
        }

        int temp =  r0 % r1;  // 取模
        r0 = r1;
        r1 = temp;

        return euclideanAlgorithm( r0, r1);
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

扩展欧几里得算法

欧拉函数

在环 Z m = { 0 , 1 ， . . . , m − 1 } Z_m={\{0,1，...,m-1\}} Zm​={0,1，...,m−1}中，如何求这个集合中有多少个数字与m互素呐？？。这个数目可以由欧拉(Euler’s Phi)函数给出，其定义如下:

欧拉函数：$Z_m$内与m互素的整数的个数可以表示为$\Phi (m)$。

$\Phi (m)$计算方法：假设m可以因式分解为以下数的连乘$$m={p_1}^{e_1}\ast {p_2}^{e_2}\ast .......\ast {p_n}^{e_n}$$其中,$p_i$表示不同元素的个数，$e_i$表示正整数，则有$$\Phi (m)=\prod _{i=1}^n({p_i}^{e_i}-{p_i}^{e_i-1})$$

示例: 假设m=240，240因式分解对应的连乘形式为:$$m=240=16\ast 15=2^4\ast 3\ast 5={p_1}^{e_1}\ast {p_2}^{e_2}\ast {p_3}^{e_3}$$其中有三个不同的质因子，即n= 3，则欧拉函数的值为$$\Phi (m)=(2^4-2^3)\ast (3^1-3^0)(5^1-5^0)=8\ast 2\ast 4=64$$这意味着在范围 { 0 ， 1 ， . . . ， 239 } \{0，1，...，239\} {0，1，...，239}内存在64个整数与m = 240互素。而替代方法需要计算240次$gcd$,也就是需要把0-239中的每个数与240进行判读是否互素，即使对较小的整数而言，这个计算过程也会非常慢。

注意： 在用这种方法快速计算欧拉函数时,前提是必须要知道m的因式分解。这个特性也是RSA公钥方案的核心; 如果已知某个整数的因式分解，就可以计算出欧拉函数并解密密文。如果因式分解未知，也就不能计算欧拉函数，也无法解密。

Java实现欧拉函数（暴力求解方式）：

/**
 * @Author Mr.Lu
 * @Date 2022/6/25 20:51
 * @ClassName EulerFunctionDemo
 * @Version 1.0
 */
public class EulerFunctionDemo {
    public static void main(String[] args) {
        System.out.println(eulerFunction(240));
    }

    /**
     * 求{0， m-1}中与m互素的个数
     * @param m
     * @return
     */
    public static int eulerFunction(int m){
        int eul = 0;  // 集合中与m互素的个数
        for(int i = 0; i < m; i++){
            if(gcd(i, m) == 1){
                eul++;
            }
        }

        return eul;
    }

    /**
     * 求r0与r1的最大公约数
     * @param r0
     * @param r1
     * @return
     */
    public static int gcd(int r0, int r1){
        // 利用位运算，始终保持 ro > r1
        if(r1 >  r0){
            r0 =  r0 ^ r1;
            r1 =  r0 ^ r1;
            r0 =  r0 ^ r1;
        }

        // 递归结束条件
        if(r1 == 0){
            return  r0;
        }

        int temp =  r0 % r1;  // 取模
        r0 = r1;
        r1 = temp;

        return gcd( r0, r1);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53

费马小定理与欧拉定理

费马小定理：假设$a$为一个整数，$p$为一个素数，则:$$a^p\equiv a(modp)$$注意，有限域$GF(p)$上的算术运算都是通过$modp$实现的，因此，对有限域$GF(p)$内的所有整数元素$a$而言，此定理始终成立。此定理也可表示为以下形式:$$a^{p-1}\equiv 1(modp)$$此等式也可以写成$$a\ast a^{p-2}\equiv 1(modp)$$这个表示形式正是乘法逆运的定义。因此，我们可以得到反转整数a模一个素数的方法$$a^{-1}\equiv a^{p-2}(modp)$$注意：只有在p为素数的时候这种反转方法才成立。

示例：假设p=7，a= 2，计算a的逆元可以表示为:$$a^{p-2}=2^5=32\equiv 4(mod7)$$结果验证: $2\ast 4\equiv 1mod7$。

将费马小定理的模数推广到任何整数模，即p不一定为素数的模，就可得到欧拉定理。

欧拉定理：假设$a$和$m$都是整数，且$gcd(a,m)=1$, 则有：$$a^{\Phi (m)}\equiv 1(modm)$$由于这个定理对模数m适用，所以它也适用于整数环$Z_m$内的所有整数。

示例：假设m = 12，a = 5。首先计算m的欧拉函数：$$\Phi (12)=\Phi (2^2\ast 3)=(2^2-2^1)(3^1-3^0)=(4-2)(3-1)=4$$验证欧拉定理：$$5^{\Phi (12)}=5^4=25^2=625\equiv 1(modm)$$费马小定理是欧拉定理的一个特例。如果p为一个素数，则$\Phi (p)=(p^1-p^0)=p-1$成立。如果将这个值用于欧拉定理，则可得到: $a^{\Phi (p)}=(p^1-p^0)=p-1$，而这正是费马小定理。

参考资料：《深入浅出密码学》–Christof Paar,Jan Pelzl著