密码学备忘录-数学基础

1. 辗转相除法（欧几里得算法 Euclidean algorithm）

  • 用途：get greatest common divisor最大公约数

gcd(a,b)=gcd(b,a%b)

1
2
3
4
5
def gcd(a, b):
    while b != 0: # 直到余数为0
        t = a % b
        a,b = b,t
    return a

1.1. 扩展欧几里得

定理：若a和b为正整数，则存在整数x,y使得gcd(a,b)=ax+by;

1
2
3
4
5
6
7
def egcd(a, b):
    """扩展欧几里得"""
    if 0 == b:
        return 1, 0, a
    x, y, q = egcd(b, a % b)
    x, y = y, (x - a // b * y)
    return x, y, q

2. 剩余类（residue class）

把所有与整数a模n同余的整数构成的集合叫做模n的一个剩余类

  • 并把a叫作剩余类[a]的一个代表元

2.1. 完全剩余系（Covering system）

如{0,1,2,3,4}是5的一个完全剩余系

3. Miller Rabin 算法(大数判断素性)

  • 有时候我们想快速的知道一个数是不是素数，而这个数又特别的大导致 O( √n) 的算法不能通过，这时候我们可以对其进行 Miller-Rabin 素数测试，可以大概率测出其是否为素数
  • 因此如果同时不满足①②的话，那就不是素数
    • 一般要选多个$a$来测试

4. Discrete Logarithms 离散对数

离散对数（英语：Discrete logarithm）是一种基于同余运算和原根的一种对数运算

  • 当模 m 有原根时，设 l 为模 m 的一个原根，则当 $x≡l^k(\bmod{m})$ 时：

  • $lnd_lx≡k(\bmod{m})$，此时$lnd_lx$即为离散对数值

5. 中国剩余定理(Chinese Remainder Theorem)

中国剩余定理说明：假设整数m1, m2, … , mn其中任两数互质，则对任意的整数：a1, a2, … , an，方程组(S)有解，并且通解可以用如下方式构造得到

The Chinese remainder theorem is widely used for computing with large integers, as it allows replacing a computation for which one knows a bound on the size of the result by several similar computations on small integers.

中国余数定理被广泛用于大整数的计算，因为它允许用小整数上的几个类似计算来代替一个知道结果大小界限的计算。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def chinese_remainder_theorem(n1: int, r1: int, n2: int, r2: int) -> int:
    """
    >>> chinese_remainder_theorem(5,1,7,3)
    31
    Explanation : 31 is the smallest number such that
                (i)  When we divide it by 5, we get remainder 1
                (ii) When we divide it by 7, we get remainder 3
    >>> chinese_remainder_theorem(6,1,4,3)
    14
    """
    (x, y) = egcd(n1, n2) 
    m = n1 * n2 
    n = r2 * x * n1 + r1 * y * n2 
    return (n % m + m) % m
  • x mod 5 = 1
  • x mod 7 = 3

6. 费马小定理&&欧拉定理

  • 参考：密码学备忘录-公钥密码
1
2
3
4
5
6
def euler(a):
    cnt = 0
    for i in range(1, a):
        if gcd(a, i) == 1:
            cnt += 1
    return cnt

7. 阶

1
2
3
4
5
6
7
8
9
10
def order(a, n, b):
    #   输出b在mod(a)中的阶
    #   n是mod(a)群的阶
    p = 1
    while p <= n and b ** p % a != 1:
        p += 1
    if p <= n:
        return p
    else:
        return -1

8. 模逆元(Modular multiplicative inverse)

在数论中，如果ab=1(mod p) ，我们就说a和b在模p意义下互为乘法逆元，记作a=inv(b) 。

8.1. egcd求逆元

9. 群（Group）

  • 在数学中，群（group）是由一种集合以及一个二元运算所组成的代数结构，并且符合“群公理”。群公理包含下述四个性质，分别是封闭性、结合律、单位元和对于集合中所有元素存在逆元素

    群包含了集合，并且有一个定义的二元运算，加运算或乘运算。而集合只是一系列元素的组成，并不包含运算

9.1. 阿贝尔群（Abelian group）

  • 又称可交换群
  • 多了一个交换律，a+b=b+a

10. 环（Ring ）

11. 域（field）

比如有理数域、实数域，总之就是一个集合

  • 在此集合上能进行“加减乘除”

11.1. 有限域（finite field）

不是所有域中都一定包含无穷多个数，也存在一些由有限多个数构成的域

  • 由有限多个数构成的域叫作「有限域」（也称“伽罗瓦域）
  • 在有限域中，数的个数最少为 2，这个域就是用 (mod 2) 对整数进行分类时的剩余类
    • 在此域上，1+1=0，例如3+3mod2=0

12. 生成元

1
2
3
定义：若一个群G的每一个元都是G的某一个固定元a的乘方，我们就把G叫做循环群；我们也说，G是由元a生成的，并且用符号
G=（a）
来表示。a叫做G的一个生成元

13. 阶（order）

13.1. 群的阶

  • 一个群的阶是指其势，即其元素的个数
  • 一个群G的阶被标记为ord(G)或|G|
  • 设n>1,a和n互质，则必有一个x (1≤x ≤n-1)使得： a^x ≡ 1 (mod n )
  • 满足a^x ≡ 1 (mod n ) 的最小整数x , 称为a模n的阶。符号表示为Ord(a)

13.2. Primitive Root 本原根

根据欧拉定理，显然我们可以知道φ(n) 是方程的一个解，但它未必是最小的，所以不一定是阶，而当φ(n) 是a模n的阶时，我们称a为n的原根

  • 原根，是一个数学符号。设m是正整数，a是整数，若a模n的阶等于φnm)，则称a为模m的一个原根