title: 素数测试 费马小定理 辗转相除法
url: 'https://yayi.site/archives/素数测试费马小定理辗转相除法'
categories: 算法与设计
cover: 'https://cdn.jsdelivr.net/gh/TangxinGH/picbed/img/动漫/結城友奈は勇者である/結城·友奈.png'
tags: 'gcd,素数测试'
abbrlink: c680ce7e
date: 2020-09-23 20:37:24

updated: 2021-05-14 22:04:55

## 素数测试

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

可以整除意味着mod为0

费马小定理

$$
p =prime number
$$

$$
n

$$

$$
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 mod | 695 = | 417 |
| :—–: | :—: | —- |
| 695 mod | 417= | 278 |
| 417 mod | 278= | 139 |
| 278 mod | 139= | 0 |
| 139 | … | GCD |

139最大公约数。

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