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

2020-05-21 本文已影响0人 SamiraG

广义欧几里得除法

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互素的整数个数，计做 $\varphi$ ，通常叫做欧拉函数。

欧拉函数性质：
假设m, n是互素的两个正整数，则
$\varphi(m*n) = \varphi(m) * \varphi(n)$

欧拉定理

(Euler) 设m是大于1的整数，如果a是满足 $(a, m) = 1$ 的整数，则
$a^{\varphi(m)} \equiv 1(mod\;m)$
但是使得 $a^e \equiv 1(mod\;m)$ 成立的最小整数e不一定是 $\varphi(m)$ , 只有 $e \leq \varphi(m)$ ，如果取等号则a称为m的原根。

费马小定理

(Fermat) 设p是一个素数，则对任意整数a，有：
$a^p\equiv a(mod\;p)$

Wilson定理

(Wilson) 设p是一个素数，则
$(p-1)! \equiv -1 (mod\;p)$

同余式

设m是一个正整数，m不是a的因子，则一次同余式 $ax \equiv 1(mod\;m)$ 有解的充分必要条件是 $(a, m) =1$

中国剩余定理

设 $m_1, m_2, m_3,...,m_k$ 是k个两两互素的正整数，则对任意的整数 $b_1, b_2, ..., b_n$ 同余式组
$x \equiv b_1(mod\;m_1)$
...
$x \equiv b_k(mod\;m_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是正整数，若同余式
$x^2 \equiv a (mod\;m),\:(a, m) = 1$
有解，则a叫做m的平方剩余(或二次剩余)；否则，a叫做模m的平方非剩余。

欧拉判别条件

设p是奇素数，(a, p) = 1, 则
(i) a是模p的平方剩余的充分必要条件是
$a^{\frac{p-1} 2} \equiv 1(mod\;p)$
(ii) a是模p的平方非剩余的充分必要条件是
$a^{\frac{p-1} 2} \equiv -1(mod\;p)$
由这个判别推出勒让得符号和雅克比符号

群

设G是一个具有结合法的非空集合，G叫做一个群，如果G中的结合法满足以下三个条件，
(i) 结合律：即对任意的 $a, b, c \in G$ ，都有
$(ab)c=a(bc)$
(ii) 单位元：即存在一个元素 $e \in G$ ，使得对任意 $a \in G$ ，都有
$ae=ea=a$
(iii) 可逆性：即对任意的 $a \in G$ ，都存在 $a' \in G$ ，使得
$aa' = a'a = e$
特别的，当G的结合法写作乘法时，G叫做乘群，当G的结合法写作加法时，G叫做加群。群G中元素的个数叫做群G的阶。

同态和同构

设G, G'都是群，f是G到G'的一个映射，如果对任意的 $a, b \in G$ ，都有
$f(a, b) = f(a) f(b)$
则f叫做G到G'的一个同态，如果f是一一对应的，则称f为同构。

环

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

域

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

多项式环

设R为整环，x为变量，则R上形为
$a_nx^n + ... + a_1x + a_0,\:\:a_i \in R$
的元素称为R上的多项式。
设 $f(x) = a_nx^n + ... + a_1x + a_0,\:\:a_i \neq R$ 是整环R上的多项式，如果再定义加法和乘法则可以生成整环R[x]
注意定义多项式环需要声明是定义在哪个环或者域上的。
$Z[x]$ ：定义在整数环上的多项式环
$F_2[x]$ ：定义在域 $F_2$ 上的多项式环
GF(2)到GF(2^8)的扩张: https://blog.openacid.com/storage/ec-2/