基础运算
Contents
目录 start
目录 end|2023-09-17 15:44|
基础运算
位运算
且 或 非 异或
模运算
整数除法：A / B = C 余 D
定义： A mod B = D 。 模运算不关注除法的结果而是关注余数。计算机上通常标识为 A%B
同余
A≡B(mod C)：A 与 B 模 C 同余
等效于
- A mod C = B mod C
- C ∣ (A − B)
| 符号意味着整除，或者前者是后者的因子 - A = B + K * C
其中 K 为整数
同余具有数学性质：反射性，对称性，传递性
- 具有反射性：A与A有关
- 具有 对称性： 如果A与B有关，那么B与A有关。
- 具有 传递性： 如果A与B有关且B与C有关，那么A与C有关。
商余定理: 给出任何整数 A 和一个正整数 B ，存在唯一整数Q和R ，满足
A = B * Q + R 其中 0 ≤ R < B. 即A mod B = R
加法
(A + B) mod C = (A mod C + B mod C) mod C
减法
(A - B) mod C = (A mod C - B mod C) mod C
可以看作加法的逆运算
乘法
(A * B) mod C = (A mod C * B mod C) mod C
除法
又称模逆运算。
指数
A^B mod C = ( (A mod C)^B ) mod C
分治法计算
当B数值很大时，中间计算值通常会溢出所有编程语言的整数类型, 此时可将幂拆分多个幂相乘。
例如： 计算 2^90 mod 13 的值。
先对指数部分做拆分： 2^50 mod 13 = 4 2^40 mod 13 = 3。简化为：
= (2^50 * 2^40) mod 13
= (2^50 mod 13 * 2^40 mod 13) mod 13
= ( 4 * 3 ) mod 13
= 12 mod 13
快速模幂运算
相较于分治法，更利于计算机计算，效率更高。
当B的值是2的幂时：
A^2 mod C = (A * A) mod C = ((A mod C) * (A mod C)) mod C
例如： 计算 7^256 mod 13 的值。
可以采用递归方式迭代计算： 先计算 7^1 mod 13 代入到 7^2 mod 13 代入到 7^4 mod 13 ...中，最终得到 7^256 mod 13 的值
当B的值是任意值时: 可以将B转换为二进制数相加 例如将 7 转换为 111 即 1+2+4
例如计算 31^7 mod 5 的值。
= 31^(1+2+4) mod 5
= 31^1 * 31^2 * 31^4 mod 5
= (31^1 mod 5 * 31^2 mod 5 * 31^4 mod 5) mod 5
问题又变成了B的值是2的幂问题进行求解，同样采用上述方式迭代计算，即可得到 31^7 mod 5 的值。
对数运算
乘方的逆运算称为对数，数学运算中求大整数的对数不会很困难，但是模运算中求的对数被称为离散对数，大整数时，离散对数计算困难和耗时，暂未发明高效的算法。
Diffie-Hellman 密钥交换协议 和 EleGamal 公钥算法中就运用了离散对数
例如：51^x mod 23 = 12 求取 x，只能暴力求解得到x=20
相关思想
扩展欧几里德算法
又称 辗转相除法，求解两个整数的最大公约数
计算 GCD(A,B) 的值，算法如下：
如果 A = 0， GCD(A,B)=B，因为 GCD(0,B)=B，我们就到此为止。
如果 B = 0，GCD(A,B)=A，因为 GCD(A,0)=A，我们就到此为止。
用商和余数的表达方式 (A = B⋅Q + R) 写出 A。
用扩展欧几里德算法计算 GCD(B,R)，因为 GCD(A,B) = GCD(B,R)
Author Kuangcp
LastMod 2023-09-10