今天花了一下午的时间学习密码学的数论部分, 下面将学到的内容进行一下总结, 也算是加深记忆. 我本身对密码学这方面比较感兴趣, 而且本节出现了许多数学公式, 使用刚刚学习的 LaTex 公式来呈现出来, 练习练习, 何乐而不为.
首先给出了群, 交换群 (阿贝尔群), 环, 交换环, 整环, 域的定义, 大致如下图所示:
涉及到的第一个重要的新概念就是有限域 $GF(p)$ Galois Fields
有限域的元素个数是一个素数的幂 $p^n$,n 为正整数, 一般记为 $GF(p^n)$, 我们最为关注的只有两种情况: n=1 即 $GF(p)$;p 为 2 即 $GF(2^n)$.
$GF(p)$ 的空间是模 p 的完全剩余类 $Z_p : \left\{0, 1, \cdots, p-1 \right\}$
$GF(2^n)$ 中的的元素是系数为二进制 0 和 1 的多项式, 最高不超过 n-1 次. 一个元素可以被表示成一个长度为 n 的位矢量. 例如二进制数 $11001_2$ 在 $GF(2^5)$ 中可以记作 $x^4+x^3+1$
这样来看,$GF(p)$ 和 $GF(2^n)$ 域中的元素都可以用多项式来表示, 一个多项式可以被表示成如下形式:$$f(x)=a_{n}x^n+a_{n-1}x^{n-1}+\cdots+a_{1}x+a_0=\sum^n_{i=0}a_{i}x^i$$
下面是重头戏, 如何计算? 针对三种不同的作用域我们定义了三种不同的多项式运算.
1. 普通多项式运算. 这个不必多说, 从小学初中就开始学, 就是我们认识的普通多项式.
2. 系数在 $Z_p$ 中的多项式运算. 和普通多项式运算不同的是, 系数要进行模 p 运算. 模可以是任意素数, 一般取二, 是最简单的情况. 例如:$$f(x)=x^3+x^2+1,\ \ g(x)=x^2+x+1\\f(x)+g(x)=x^3+x,\ \ f(x)\times g(x)=x^5+x+1$$
可见多项式的系数在运算的时候进行了模 2 处理.
3. 有限域 $GF(2^n)$ 上的多项式运算. 这种运算和计算机的运作方式很相似, 对于一个有限域 $GF(2^n)$ 我们定义如下要求: 系数对 2 取模运算, 最高次数小于 n, 多项式对 n 次素多项式取模运算. 既然是域那就有逆元, 可以用拓展欧几里得算法求逆.
来源: http://www.bubuko.com/infodetail-3236101.html