471 字

2 分钟

数论

2024-04-18

数论

密码学基础#

Euclid欧几里得算法（求最大公因数）#

又叫做辗转相除法

如： $gcd(18, 12) \to gcd(12, 6) \to gcd(6, 0)$

1
int Euclid(int a, int b){
2
    if(b == 0){
3
        return a;
4
    }
5
    a = a % b;
6
    return Euclid(b, a);
7
}

若a 与 n 互素：如果(a * b) = (a * c) mod n，则b = c mod n，其中等号表示mod n同余

给定两个整数 $a$ , $b$ ，可以表示为 $ax + by(x, y \space can \space be \space negative)$ 的最小正整数等于 $gcd(a, b)$

若p是素数，且a是不能被p整除的正整数，那么：

a^{p - 1} = 1(mod \space p)

欧拉函数： $\phi(n)$ ，表示小于n的互素的正整数个数。如 $\phi(10)=5$ ，即：1,2,3,7,9

一般：

$\phi(1)=1；$

$\phi(n)=n-1$ （n是素数）

费马定理： $a^{n - 1} = 1(mod \space n)$

欧拉函数： $\phi(n)=n-1$ (n为素数)

将费马定理和欧拉函数可得：

a^{\phi(n)} = 1(mod \space n)

奇整数分解公式：如果 $n \ge 3$ ，且是奇数

n - 1 = 2^{k}q, (k>0,q \% 2 = 1)

模的乘法公式： $[(a \% n) * (b \% n)] \% n = (a * b) \% n$

由欧拉定理： $a^{\phi(n)} = 1(mod \space n)$

$a^{\phi(n)} \space mod \space n = a^{2^{k}q} \space mod \space n = a^q \space mod \space n = 1$

从而所有的 $a^q$ 的乘积 $mod \space n$ 都为1，即：

$a^q \space mod \space n = a^{2q} \space mod \space n = a^{2^2 q} \space mod \space n = ... = a^{2^k q} \space mod \space n = 1$

因此：如果n是素数，那么遍历这些数，只要有mod n不为1，就是合数。

数论

作者

Zheyv

发布于

2024-04-18

许可协议