Blockchain Tool

哈希算法
- Hash256
- Hash160
- Tagged Hash
- Keccak256
密码学
- 椭圆曲线
  - ECC基础
  - ECC常用操作
  - Secp256k1
  - Twisted Edwards
  - 基于椭圆曲线的签名算法
    - ECDSA
    - EdDSA
    - Schnorr
  - 基于椭圆曲线的密钥交换
    - ECDH
地址
- Bitcoin
  - 公钥生成
  - Base58
  - Bech32
  - Bech32m
  - WIF私钥
  - 助记词转化(待定...)
  - Opcode列表
- Ethereum
- Solana
通用
- 进制转换
- 字节与Ascii转换
- 小端字节序
- Compact Size
数学
- 基础
- 模运算(理论)
- 模运算

v0.0.1

模运算

取模运算(多用于计算机)与取余运算(多用于数学概念) 有重叠当不完全一致，

主要区别在于对负整数进行除法运算时操作不同, 对于正整数两者结果一致。

取模运算对于负数是向负无穷的方向舍入，如 -7 % 4 = 1

计算步骤:

1. 求整数商 c = a/b = -7/4 = -1.75 = -2 ( 此时向负无穷的方向舍入！！)

2. 计算模和余数 m = a - b * c = -7 - (4 * -2) = 1

取余运算对于负数是向0方向舍入，如 -7 % 4 =-3

计算步骤:

1. 求整数商 c = a/b = -7/4 = -1.75 = -1 ( 此时向0方向舍入！！)

2. 计算模和余数 m = a - b * c = -7 - (4 * -1) = -3

可以看出主要是计算出商的结果导致取模和取余的结果不一致

不同的编程语言 %运算符的含义也有所不同, 比如c/c++, java, javascript 为取余, 而python则为取模

即 python中执行 -7 % 4 结果是 1

javascript 中执行结果是-3

取模运算的结果一定是非负数

对应 % 是取余运算的编程语言可以使用【

a % p = (a mod p + p) mod p

】来转成取模运算

例如 -7 % 4 = ((-7 % 4) +4) %4 = 1 (在javascript环境下的%)

对应 % 是取模运算的编程语言可以使用【

a % p = a - (a/p 的商, 不是余数) * p

】来转成取余运算

例如 -7 % 4 = -7 - (-7 /4 的商, -1.75 向0方向舍入, 即 -1 ) *4 = -3 (在python环境下的%)

前置知识点:

p | a 表示 p 能整除(即余数0) a，即 a 是 p 的倍数。例如: 7|21 、 5|20 、 3 |10 (因为3不能整除10)
同余数: 正整数a, b对p取模, 它们的余数相同, 记做
$a \equiv b % p$ 或者 $a \equiv b (mod p)$ (ps: 注意"≡", a ≡ b mod p ,对应的是 a mod p = b mod p )
正负只有除数相关: n % p 正负由被除数n决定,与p无关, 例 7 % 4 = 3, -7 % 4 = -3, 7 % -4 = 3, -7 % -4 = -3

性质:

若 p|(a-b), 则 a ≡ b mod p。例如 "7|(11-4)" 等同 "11 ≡ 4 mod 7" 即 "11 mod 7 = 4 mod 7"
a ≡ b(mod n) 的充要条件(充分必要) a - b = n * x, 其中x是未知数, 即 a-b 是 n 的倍数
自反性: 所有实数a, 都有 "a ≡ a (mod n)"
对称性: 若 "a ≡ b (mod n)", 则"b ≡ a (mod n)"
传递性: 若"a ≡ b mod p" 且 "b ≡ c mod p" ，则 "a ≡ c mod p"

模运算的实际应用:

时钟 17点是几点? 17 % 12 = 5, 下午5点

奇偶数判断: x % 2 结果 0 则是偶数 1 则是奇数

素数的判断 x % {0,1,...i} 遍历，如果有取模等于0时非1或者本身, 则是非素数

...

(a + b) mod p = ((a mod p) + (b mod p)) mod p

(a - b) mod p = ((a mod p) - (b mod p)) mod p

⚠️由于 "a - b" 可能是负数，所以可以加上 "+p" 以确保结果非负

(a - b) mod p = ((a mod p) - (b mod p) + p) mod p

(a \times b) mod p = ((a mod p) \times (b mod p)) mod p

⚠️ 注意上面的加法、减法、乘法公式最终都得再 mod p

例如: 加法运算当 a = 7, b = 8, p = 10 如果右侧的

(a mod p) + (b mod p)

超过 p 时，等式不成立

a * x \equiv 1 (mod p)

其中 x 称为 a在模p下的逆元(前提条件是a 和 p需互质(互素)！) 即

a^{- 1} \equiv x (mod p) ⟺ a^{- 1} mod p = x mod p

原理:

如果 a = 3, p = 5的情况下

3 * x \equiv 1 (mod 5)

根据自反性

a \equiv a (mod n)

, 可得

x = 3^{- 1}

因为

1 \equiv 1 (mod 5)

即

3 * 3^{- 1} \equiv 1 (mod 5)

此时只要找到一个正整数 x 使

3 * x \equiv 1 (mod 5)

即可替代掉

3^{- 1}

可以计算的出 x = 2 满足该条件

3 * 2 mod 5 = 1

1 mod 任何数都为1, 可得

3 * 2 mod 5 = 1 mod 5 ⟺ 3 * 2 \equiv 1 (mod 5)

最终 :

3 * 2 \equiv 1 (mod 5)

和

3 * 3^{- 1} \equiv 1 (mod 5)

可以看出此时

2 和 3^{- 1}

可平替

性质:

互为逆元: a 在模p 下有逆元 x，那么 x在模p下逆元即是 a

逆元唯一: a 在模p 下乘法逆元是唯一的，如模5 下 2 和3 互为逆元，且没有别的逆元了！！

逆元可能是本身:

如 1在不管模哪个整数，都以自己为逆元;

模5的情况下, 4 * 4等于1, 即模5下 4的乘法逆元即为本身;

模4的情况下 3 * 3等于1, 即模4下 3的乘法逆元为本身

乘法逆元不一定存在，需 “gcd(a,p) =1” ,即a和 p最大公约数是1(互素), 模n下才会有 a的乘法逆元

例如 2 * x ≡ 1 (mod 4), 此时在模4下不存在2的乘法逆元 1 mod 4则一定是奇数，而 2 * x 一定是偶数所以该条件不成立

求模逆:

1. 扩展的欧几里得算法

设a和b的最大公约数是d即 `gcd(a,b) = d` 那么一定存在两个数 s 和t 使得

a * s + b * t = d

即

g c d (a, b) = a * s + b * t

扩展的欧几里得算法就是为了算出这个 s 和 t

回到求模逆，前提条件就需要 `gcd(a,p) = 1` 代入

a * s + p * t = 1

此时两边同时进行模 p 处理可得

(a * s + p * t) mod p = 1 mod p

此时 p * t 正好是 p的整数倍 mod p后就得0了, 所以简化后

a * s mod p = 1 mod p

可以看出模 n 下a的逆元就是 s，使用扩展的欧几里得算法可求出s

2. 快速幂法(费马定理)

待定...

要计算：

\frac{a}{b} mod p

由于不能直接除法，可以转换为乘法：

(a \times b^{- 1}) mod p ⟺

其中

b^{- 1}

是 b 在模 p 下的乘法逆元。

例如:

(14/4) mod 5

可化简为

7 * 2^{- 1} mod 5

此时根据模逆

2 * 3 \equiv 1 mod 5

可得

7 * 3 mod 5

最终结果为 1

Blockchain Tool

模运算

取模运算与取余运算

基本性质

前置知识点:

性质:

模加法(Modulo Addition)

模减法(Modulo Subtraction)

模乘法(Modulo Multiplication)

⭐️ 模乘法逆元(Modular Inverse)

模除法(Modulo Multiplication)

模运算