信息安全的数学基础

第一章 整数与二进制

\[ Z:整数\quad N：自然数\quad Q：有理数\quad R：实数\quad C：复数 \]

1.1 二进制

1.二进制是计算技术中广泛采用的一种数制。二进制数据是用0和1两个数码表示的数。它的基数为2，进位规则是“逢二进一”，计算机内部只有二进制。

2.为了区分十进制和二进制，通常会在二进制数值前加上ob标识以示区分。

  1. $$ \begin{equation} \begin{split} 二进制性质一:偶数二进制最末尾的比特是0，奇数二进制末尾的比特是1。

\end{split} \end{equation} $$

  1. \[ 二进制性质二:在一个二进制末尾增添一个0等同于在十进制中对这个数乘以2,\\反过来说，对一个十进制数乘以2操作等同于对其二进制表达式左移一个比特。 \]
  2. \[ \\二进制性质三:给定任意自然数，十进制数2^n的二进制数表达式就是在1后面加n个0：ob\underbrace {1000000....0}_{n} \]
  3. \[ 二进制性质四:给定任意自然数，十进制数2^n-1的二进数表达式就是n个1，ob \underbrace {11111111.....1}_n \]
  4. \[ 位置计数法： b=\sum\limits_{i=0}^{n-1}b_i2^i \quad\\ b为整数，n为b的比特长度，b_i\in{0,1}可以视为取舍的标识。 \]
1.2 加法与乘法

位运算：

位运算是按照二进制进行的运算，c语言提供6个位运算操作符，这些操作符适用于整型操作数。具体6个操作符如下：

符号 名称 含义
& 按位与 两个相应的二进制位都为1，该位的结果值为1
| 按位或 两个相应的二进制位中只要有一个为1，该位的结果值为1
^ 按位异或 两个相应的二进制位值相同则为0，否则为1
~ 取反 一元运算符，对一个二进制数按位取反，将0变1，将1变0
<< 左移 将一个数的各二进制位全部左移N位，右补0
>> 位运算 是按照二进制进行的运算，c语言提供6个位运算操作符，这些操作符适用于整型操作数

  • 按位与&：参与运算的两个数按照二进制位依次进行与运算，即两位都是1结果为1，否则为0；可用于清零，保留指定位。

    1.清零：想将原数清零，只需要原数中所有为1的位，在新数中对应为0，两数进行&操作即可为0000000

    2.保留指定位：想保留原数的第n位，只要新数的第n位保证为1,两数&操作即可保留原数的第n位，想保留多位按此操作也可。

  • 按位异或^:参与运算的两个数对应的二进制数相同为0，不同为1.

  • 左移<<:根据指定位数将原数各个二进制位左移至指定位，高位左移溢出则舍弃，低位空位用0补齐。当该数左移时溢出舍弃的高位中不包含1时，左移类似乘法，左移n位相当于该数乘以2^n.

一个新算法必须要考虑的三个关键要素：正确性、效率和优化。

1.3 除法算法

\[ \begin{split} 定理1.1-除法算法： \\对任意给定的整数a和b,其中b>0,存在唯一的整数q(商)和r(余数)使得，a=qb+r,且0\leq r \leq b. \end{split} \]

公理1.1良序原则：

自然数的非空子集必然存在一个最小的元素。

如何证明？......

一些常用术语：

b|a:a可以被b整除，a=qb; 如果整数d满足d|a且d|b,则称d为a和b的公因子，如果d是a和b的公因子，并且对于a和b的其他d'，都有d’|d,则称d为a和b的最大公因子，记d=gcd(a,b). 如果gcd(a,b)=1,则称a,b互素。

第二章 欧几里得算法及相关定理

2.1欧几里得算法

欧几里得算法是计算两个整数的最大公因子，也简记为gcd算法。 \[ 定理2.1 欧几里得算法： \\ 给定两个整数a和b,设a\ge b，则a和b的最大公因子等于b和amodb的最大公因子\\ 即gcd(a,b)=gcd(b,amodb),其中，amodb表示a除以b所得到的余数r。 \]

引理：如果a>=b,则（amodb)<a/2。

2.2扩展欧几里得算法（egcd)

此算法还可以计算出这个公因子如何表达为a和b的线性组合。 $$ Bézout 定理

设 a 和 b 为非零整数，存在整数 r和 s 使得：

gcd(a, b) = ar + bs

而且，a 与 b 的最大公因子是惟一的。称 r和 s为 Bézout 系数 $$

群

1.1集合

近世代数是纠错码和密码学的重要数学基础

具有共同属性的事物的总体

定义（集合上的二元运算）

设S为集合，映射： \[ \eta: \left\{ \begin{array}{**lr**} S × S\dashrightarrow S \\ (x,y)\dashrightarrow z \end{array} \right. \] 称为集合S上的二元运算。

群（定义）

\[ \begin{flalign} 设三元组(G,\cdot,1)中G为集合，\cdot为集合G上的二元运算，1为G中一个元。若（G，\cdot,1）满足：\\ 1.G1(乘法结合律)：a\cdot(b\cdot c)=(a\cdot b)\cdot c;a,b,c\in G \\ 2.G2(单位元)：1\cdot a=a \cdot 1,a \in G \\ 3.G3(逆元)：对a \in G,有a' \in G,使得a\cdot a'=a' \cdot a=1.\\ 则称(G,\cdot,1)为群，简称群G，1称为群G的单位元，a'称为a的逆元。\\ 4.如果满足G4(交换律)，则称G为交换群。\\ 5.若仅满足G1,G2,则称G为有单位元的半群。\\ 6.若仅满足G1,G2,G4,则称G为有单位元的交换半群。 \end{flalign} \]

例子：希尔密码

定理

\[ \begin{split} 设A=(a_{ij})为一个定义在Z_{26}上的n*n矩阵，若A在mod26上可逆，则有:\\ A^{-1}=(detA)^{-1}A*(mod26)\\ 这里，A*是A的伴随矩阵 \end{split} \]

子群

\[ 设（G，\cdot,1）为群，A为G的子集合。若1\in A且（A,\cdot,1）构成群，则称A为G的子群，\\ 并记为A\leq or \le G。 \]