信息安全数学基础

EP 收录于 notes

2020-05-21 约 1529 字预计阅读 4 分钟

广义欧几里得除法

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
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)$
一定有解，且解唯一。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
# 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/

目录