6.3 公钥算法的基本数论知识(欧几里得算法、扩展欧几里得算法、欧拉函数、费马小定理与欧拉定理)

• 欧几里得算法
• 扩展欧几里得算法
• 欧拉函数
• 费马小定理与欧拉定理

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

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

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

示例: 假设 r 0 = 84 ， r 1 = 30 r_0=84， r_1=30 r0​=84，r1​=30，则 r 0 − r 1 r_0 - r_1 r0​−r1​与 r 1 r_1 r1​的gcd为:
r 0 − r 1 = 84 − 30 = 54 = 2 ∗ 3 ∗ 3 ∗ 3 r_0 - r_1 = 84 - 30 = 54 = 2 * 3 * 3 * 3 r0​−r1​=84−30=54=2∗3∗3∗3 r 1 = 30 = 2 ∗ 3 ∗ 5 r_1 = 30 = 2 * 3 * 5 r1​=30=2∗3∗5
最大公因子仍然是： 2 ⋅ 3 = 6 = g c d ( 30 , 54 ) = g c d ( 30 , 84 ) 。 2·3 = 6 = gcd(30,54) = gcd(30,84)。 2⋅3=6=gcd(30,54)=gcd(30,84)。

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

解： g c d ( 973 , 301 ) = g c d ( 301 , 973 m o d 301 ) = g c d ( 301 , 70 ) = g c d ( 70 , 301 m o d 70 ) = g c d ( 70 , 21 ) = g c d ( 21 , 70 m o d 21 ) = g c d ( 21 , 7 ) = g c d ( 7 , 21 m o d 7 ) = g c d ( 7 , 0 ) = 7 gcd(973, 301) = gcd(301, 973 mod 301) = gcd(301, 70) = gcd(70, 301 mod 70) = gcd(70, 21) = gcd(21, 70 mod 21) = gcd(21, 7) = gcd(7, 21 mod 7) = gcd(7, 0) = 7 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实现欧几里得算法：

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);
    }
}

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

欧拉函数： Z m Z_m Zm​内与m互素的整数的个数可以表示为 Φ ( m ) Phi(m) Φ(m)。

Φ ( m ) Phi(m) Φ(m)计算方法：假设m可以因式分解为以下数的连乘 m = p 1 e 1 ∗ p 2 e 2 ∗ . . . . . . . ∗ p n e n m={p_1}^{e_1}*{p_2}^{e_2}*.......*{p_n}^{e_n} m=p1​e1​∗p2​e2​∗.......∗pn​en​其中, p i p_i pi​表示不同元素的个数， e i e_i ei​表示正整数，则有 Φ ( m ) = ∏ i = 1 n ( p i e i − p i e i − 1 ) Phi(m)=quad prod_{i=1}^n({p_i}^{e_i} - {p_i}^{e_i-1}) Φ(m)=i=1∏n​(pi​ei​−pi​ei​−1)

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

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

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

public class EulerFunctionDemo {
    public static void main(String[] args) {
        System.out.println(eulerFunction(240));
    }

    
    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;
    }

    
    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);
    }
}

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

示例：假设p=7，a= 2，计算a的逆元可以表示为: a p − 2 = 2 5 = 32 ≡ 4 ( m o d 7 ) a^{p-2} = 2^5 = 32 equiv 4(mod 7) ap−2=25=32≡4(mod7)结果验证: 2 ∗ 4 ≡ 1 m o d 7 2*4 equiv 1mod7 2∗4≡1mod7。

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

欧拉定理：假设 a a a和 m m m都是整数，且 g c d ( a , m ) = 1 gcd(a, m)=1 gcd(a,m)=1, 则有： a Φ ( m ) ≡ 1 ( m o d m ) a^{Phi(m)} equiv 1(mod m) aΦ(m)≡1(modm)由于这个定理对模数m适用，所以它也适用于整数环 Z m Z_m Zm​内的所有整数。

示例：假设m = 12，a = 5。首先计算m的欧拉函数： Φ ( 12 ) = Φ ( 2 2 ∗ 3 ) = ( 2 2 − 2 1 ) ( 3 1 − 3 0 ) = ( 4 − 2 ) ( 3 − 1 ) = 4 Phi(12) = Phi(2^2*3) = (2^2 - 2^1)(3^1 - 3^0) = (4 - 2)(3 - 1) = 4 Φ(12)=Φ(22∗3)=(22−21)(31−30)=(4−2)(3−1)=4验证欧拉定理： 5 Φ ( 12 ) = 5 4 = 2 5 2 = 625 ≡ 1 ( m o d m ) 5^{Phi(12)} = 5^4 = 25^2 = 625 equiv 1(mod m) 5Φ(12)=54=252=625≡1(modm)费马小定理是欧拉定理的一个特例。如果p为一个素数，则 Φ ( p ) = ( p 1 − p 0 ) = p − 1 Phi(p) = (p^1 - p^0) = p - 1 Φ(p)=(p1−p0)=p−1成立。如果将这个值用于欧拉定理，则可得到: a Φ ( p ) = ( p 1 − p 0 ) = p − 1 a^{Phi(p)} = (p^1 - p^0) = p - 1 aΦ(p)=(p1−p0)=p−1，而这正是费马小定理。

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