每日总结-第四十天-信息安全数学基础

广义欧几里得除法

a = q * b + c, 0 <= c < b; 则(a, b) = (b, c)，可以用来计算最大公因数

def gcd(a, b):  # a <= b
    if a * b == 0:
        return 0
    r = b // a
    c = b % a
    while c != 0:
        # print("%d = %d * %d + %d"%(b, r, a, c))
        b = a
        a = c
        r = b // a
        c = b % a
    return a

算数基本定理

任意整数n > 1都可以表示成素数的乘积， 且在不考虑乘积顺序的情况下，该表达式唯一。

欧拉函数

设m是一个正整数，则m个整数1,2,3...m中，与m互素的整数个数，计做，通常叫做欧拉函数。

欧拉函数性质：
假设m, n是互素的两个正整数，则

欧拉定理

(Euler) 设m是大于1的整数，如果a是满足的整数，则

但是使得成立的最小整数e不一定是, 只有，如果取等号则a称为m的原根。

费马小定理

(Fermat) 设p是一个素数，则对任意整数a，有：

Wilson定理

(Wilson) 设p是一个素数，则

同余式

设m是一个正整数，m不是a的因子，则一次同余式有解的充分必要条件是

中国剩余定理

设是k个两两互素的正整数，则对任意的整数同余式组

...

一定有解，且解唯一。

# sage
def CRT(mi, ai):
    assert(isinstance(mi, list) and isinstance(ai, list))
    assert(reduce(gcd, mi) == 1) # mi之间互素
    M = reduce(lambda x, y: x * y, mi)
    ai_ti_Mi = [a * (M // m) * inverse_mod(M // m, m) for (m, a) in zip(mi, ai)]
    return reduce(lambda x, y: x + y, ai_ti_Mi) % M
# sage中也有crt函数
# sage: x = crt(2, 1, 3, 5); x
# 11

平方剩余

设m是正整数，若同余式

有解，则a叫做m的平方剩余(或二次剩余)；否则，a叫做模m的平方非剩余。

欧拉判别条件

设p是奇素数，(a, p) = 1, 则
(i) a是模p的平方剩余的充分必要条件是

(ii) a是模p的平方非剩余的充分必要条件是

由这个判别推出勒让得符号和雅克比符号

群

设G是一个具有结合法的非空集合，G叫做一个群，如果G中的结合法满足以下三个条件，
(i) 结合律：即对任意的，都有

(ii) 单位元：即存在一个元素，使得对任意，都有

(iii) 可逆性：即对任意的，都存在，使得

特别的，当G的结合法写作乘法时，G叫做乘群，当G的结合法写作加法时，G叫做加群。群G中元素的个数叫做群G的阶。

同态和同构

设G, G'都是群，f是G到G'的一个映射，如果对任意的， 都有

则f叫做G到G'的一个同态，如果f是一一对应的，则称f为同构。

环

设R是具有两种结合法(通常表示为加法和乘法)的非空集合，如果以下条件成立：
(i) R对于加法构成一个交换群
(ii) (结合律) 对任意的，有
(iii) (分配律) 对任意的，有
和
则R称为环。(即加法构成交换群，乘法满足结合率，加法乘法满足分配律)
(iv) 对任意的，有，则R叫做交换环
(v) 对任意的，有，则R叫做有单位元环。

域

称交换环K为一个域，如果K中有单位元，且每个非零元都是可逆元，即K对于加法构成一个交换群，对于乘法构成一个交换群。域

多项式环

设R为整环，x为变量，则R上形为

的元素称为R上的多项式。
设是整环R上的多项式，如果再定义加法和乘法则可以生成整环R[x]
注意定义多项式环需要声明是定义在哪个环或者域上的。
：定义在整数环上的多项式环
：定义在域上的多项式环
GF(2)到GF(2^8)的扩张: https://blog.openacid.com/storage/ec-2/