287 总字数
1分钟 预计时间
发布 2020-09-23
更新于 2021-05-14

## 素数测试

素数除了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次幂的情况下,判断为素数。

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


辗转相除法

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

112 mod695 =417
695 mod417=278
417 mod278=139
278 mod139=0
139...GCD

139最大公约数。

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