应用密码学-数学基础1

参考视频：
https://www.bilibili.com/video/BV1234y1m7Xs/

欧几里得算法

这个可以用于求解两个数的最大公约数。
对任何非负整数a和非负整数b:

$$gcd(a,b)=gcd(b,a \mod b)\quad(a≥b)$$

直到 a mod b = 0 时，b 即为最大公约数

扩展欧几里得算法

求解诸如这样的问题：

$$20^{-1}\mod 117=?$$

此为求乘法逆元，等价为求下面的 x 值

$$a x \equiv 1 \pmod p$$

$$a=20,p= 117;$$

此题答案为 41

使用了辗转相除法，有关例题如下：

• 视频节点：06:25

需要注意的是这个最终结果尽量写成

$$1=a*x-p*n$$

的形式，如果 x 是负数，可以加一个 p 值转换为正数。

费马(Fermat)小定理

定义

如果p是素数并且a是不能被p整除的正整数,那么，

$$a^{p-1}\equiv 1 \pmod p$$

费马定理的另一种形式：
如果

$$gcd(a,p)=1$$

则

$$a^{p}\equiv a\pmod p$$

$$a^{p-1} mod p$$

例题

a=7, p=19, 求

$$a^{p-1} mod p$$

可得答案为 1 。

欧拉函数