应用密码学-数学基础1

三葉Leaves Author

2025-02-11 2025-02-11 创建 2026-01-13 15:50:34 2026-01-13 15:50:34 更新

218 字 1 分钟

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

欧几里得算法

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

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

求解诸如这样的问题：

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

此题答案为 41

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

需要注意的是这个最终结果尽量写成
$$
1=ax-pn
$$
的形式，如果 x 是负数，可以加一个 p 值转换为正数。

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

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

则

a=7, p=19, 求

可得答案为 1 。