素数测试 费马小定理 辗转相除法

## 素数测试

素数除了1和自己外没有除数的自然数 n>1

可以整除意味着mod为0

费马小定理

$$
p =prime number
$$

$$
n<p
$$

$$
n^p \ \ mod \ \ p = n
$$

如： 113

1. 随机选取三个小于113的数字

   提高到113次幂后，得到除以113的余数。
   $$
   64^{113} \ \ mod \ \ 113 = 64\
   29^{113} \ \ mod \ \ 113 = 29\
   15^{113} \ \ mod \ \ 113 = 15\
   $$

在任何数字中，原始数字都与其余数相匹配。确认的次数越多就越高。但这是不可能的，太耗时了。于是有了改进版的：米勒-拉宾素性检验，使用于确定RSA算法中的素数。

重复该实验，在不是素数的概率比0.5的80次幂的情况下，判断为素数。

其实，即使满足所有费马素性检验，也不能确认它是素数。如果判断合数则会卡隹。

辗转相除法

两个数的最大公约数。默认方法是共同素数的最大公约数。

139最大公约数。

==可以看到除数和余数 再一次 mod==
直到为0