在这记录一些做crypto时百度到的基本的概念及实现方法,以便随时查阅,持续补充。

最基本的求余

(1) (a + b) mod p = (a mod p + b mod p) mod p
(2) (a - b) mod p = (a mod p - b mod p) mod p
(3) (a * b) mod p = (a mod p * b mod p) mod p

欧几里得算法

也称辗转相除法,计算两个正整数的最大公约数,当较小整数为0时,则表明上一次相除已除尽,所以上一次相除时的除数(当次输入的gcd函数中的较大数)是最大公约数。计算公式:

​ gcd(a,b) = gcd(b,a mod b)

a>b且a mod b不为0。

python递归实现:

1
2
3
4
5
6
7
8
9
10
def gcd(a, b):
if a < b:
a, b = b, a
while b != 0:
a,b = b,a%b
return a

a = gcd(6,18)

print(a)

乘法逆元

正整数 a, n,如果有 ax = 1(mod n),则称 x 的最小正整数解为 a 模 n的逆元。也就是说a和x的乘积模n得到的余数为1,

关于它的作用及推导过程:乘法逆元的作用

拓展欧几里得算法

在已知a,b两个正整数和欧几里得求得最大公约数d=gcd(a,b)的基础上,存在整数x,y使得ax+by=d成立,也就是 ax+by=gcd(a,b),如果a,b都是素数,则ax+by=1成立。

python实现(求逆元):

1
2
3
4
5
6
7
8
9
10
11
12
def myExtGCD(a, b):
"""
a: 模的取值
b: 想求逆的值
"""
if (b == 0):
return 1, 0, a
x, y, gcd = myExtGCD(b, a % b)
return y, x-a//b*y, gcd


print(myExtGCD(717, 73)[1] % 717)

关于逆元的求解,也可直接导入gmpy2库的invert()函数,同样可得到结果,用法:

1
2
3
4
5
6
7
8
from gmpy2 import invert()

ni = invert(a,b)
"""
a为想逆的值
b为模的取值
"""
print(ni)

费马小定理

当有两数a,p满足gcd(a,p)=1,p是质数时,则有 a^{p-1} = 1 (mod p)

这里可以变形一下,a*a^{p-2} = 1(mod p)

所以a^(p-2)就是a关于p的逆元,再用快速幂即可求得逆元(直接pow())

欧拉函数

用希腊字母φ表示,φ(N)表示N的欧拉函数,通俗地理解为小于N且与N互质的数的个数(包含1).

通式:φ(n)=n(1-1/p1)(1-1/p2)(1-1/p3)(1-1/p4)……(1-1/pn)

(1) p^k型:

若N是质数p(即N=p), φ(n)= φ(p)=p-p^(k-1)=p-1。

若N是质数p的k次幂(即N=p^k),φ(n)=p^k-p^(k-1)=(p-1)p^(k-1)。

(2)mn型

设n为正整数,以φ(n)表示不超过n且与n互素的正整数的个数,称为n的欧拉函数值。若m,n互质,φ(mn)=(m-1)(n-1)=φ(m)φ(n)。

欧拉定理及推论

欧拉定理: 若正整数a,n互质,则a^{φ(n)}≡1 (mod n),φ(n)为欧拉函数

推论:若n=pq,p≠q都是素数,k是任意整数,则mk(p-1)(q-1)+1 ≡ m mod n

​ 对任意0≤m≤n,只要选择e,d,满足ed=kφ(n)+1,即ed ≡ 1 mod φ(n) ,d ≡ e-1 mod φ(n)

待补充