密码学学习笔记(七)：Modular arithmetic

简介

模算术是整数的一种算术结构，其中数字在达到特定值时“环绕”。模运算使我们能够简单地生成群、环和域，这是大多数现代公钥密码系统的基本构造部分。其中数字超过一定值后（称为模）后会“卷回”到较小的数值。

模算数常见的应用在十二小时制，将一天分为二个以十二小时计算的单位。

模算术运算

假设这有一个13点的时钟：

设有一个小于p的整数集： $Z_{p}$ = {0,1,2,...,? − 1｝

上图中p=13，所以： $Z_{13}$ = {0,1,2,...,12}

加运算：先加然后求余数模p（即除以p）

5 + 7 = 12 ??? 13

这里12小于13所以5+7等于12不用考虑mod。

7 + 12 = 6 ??? 13

这里原本的7 + 12 = 19，因为19超出了mod 13所以19 / 13 = 1 余6，这里还可以通过上方时钟来结合看，如果一开始指针在7点，当过了12个小时之后指针会落在6点。

乘运算：先乘然后求模p的余数

2 × 5 = 10 ??? 13

小于13所以直接得10

5 × 7 = 9 ??? 13

5 x 7本来等于35，35 / 13 = 2 余9

减运算：加法的逆运算

12 − 7 = 5 ??? 13

小于13所以直接得5

6 − 12 = 7 ??? 13

可以反过来想，12+几等于6，因为模13，所以+1之后得0。1 + 6 = 7，所以等于7。

除运算：乘法的逆运算

10 ÷ 5 = 2 ??? 13

小于13所以直接得2

9 ÷ 7 = 5 ??? 13

可以反过来想，设5=n，7n mod 13 余9，相当于就是7n / 13余9

逆乘法

如果x*y = 1 mod p那么在 $Z_{p}$ 中，x和y互为倒数。

y只有在gcd(?, ?) = 1的时候存在

逆可用于计算除法：

如果? 是质数，每个? 在里面 $Z_{p}$ 除了零点外还有一个倒数。

比如：

在 $Z_{7}$ 中，(1,1)，(2,4)，(3,5)，(6,6)都互为倒数。

指数和生成器

指数：重复乘法

比如

生成器：通过求幂生成整个组的元素

比如2就是的生成器。

代表所有在 $Z_{p}$ 中可逆的元素

Fermat’s Little Theorem - 费马小定理

如果p是质数，则

所以mod(p-1)可以用指数运算。

比如：

对于生成器?, 选择一个随机指数?: $g^{a}$ 将是随机的。

文章来源地址https://uudwc.com/A/jAxJY

密码学学习笔记(七)：Modular arithmetic - 模算数

简介