物联网网络安全乘法逆元计算
物联网网络安全中乘法逆元与扩展欧几里得算法的题解。
[!info] related notes
物联网网络安全乘法逆元计算
这是一个标准的**扩展欧几里得算法（Extended Euclidean Algorithm）**应用题。
我们需要求解 $x$，使得：
$$ 53x \equiv 1 \pmod{1998} $$
即找到整数 $x$ 和 $k$，满足贝祖等式：
$$ 53x + 1998k = 1 $$
以下是详细步骤：
第一步：辗转相除法 (求 GCD)
利用大数除以小数，直到余数为 0。
-
$1998 \div 53 = 37 \dots 37$
- 式①：$1998 = 37 \times 53 + 37$
-
$53 \div 37 = 1 \dots 16$
- 式②：$53 = 1 \times 37 + 16$
-
$37 \div 16 = 2 \dots 5$
- 式③：$37 = 2 \times 16 + 5$
-
$16 \div 5 = 3 \dots 1$
- 式④：$16 = 3 \times 5 + 1$
-
$5 \div 1 = 5 \dots 0$
- (结束，最大公约数为 1，说明逆元存在)
第二步：回代 (扩展欧几里得)
利用上面的式子，从余数 1 开始逆向推导，将 1 表示为 53 和 1998 的线性组合。
-
由式④可得：
$$
1 = 16 - 3 \times 5
$$
- 代入 5 (由式③: $5 = 37 - 2 \times 16$)：
$$
1 = 16 - 3 \times (37 - 2 \times 16)
$$ 整理（合并 16）：
$$
1 = 16 - 3 \times 37 + 6 \times 16
$$ $$
1 = 7 \times 16 - 3 \times 37
$$ 3. 代入 16 (由式②: $16 = 53 - 1 \times 37$)：
$$
1 = 7 \times (53 - 1 \times 37) - 3 \times 37
$$ 整理（合并 37）：
$$
1 = 7 \times 53 - 7 \times 37 - 3 \times 37
$$ $$
1 = 7 \times 53 - 10 \times 37
$$ 4. 代入 37 (由式①: $37 = 1998 - 37 \times 53$)： $$
1 = 7 \times 53 - 10 \times (1998 - 37 \times 53)
$$ 整理（合并 53）：
$$
1 = 7 \times 53 - 10 \times 1998 + 370 \times 53
$$ $$
1 = 377 \times 53 - 10 \times 1998
$$
第三步：得出结果
由上式 $1 = 377 \times 53 - 10 \times 1998$ 可知： $$
377 \times 53 \equiv 1 \pmod{1998}
$$ 因此，53 关于模 1998 的乘法逆元是 377。
第四步：验证
计算 $53 \times 377$ 是否模 1998 余 1。
- 直接相乘： $$
53 \times 377 = 19981
$$ 2. 做除法： $$
19981 \div 1998 = 10 \dots 1
$$ 或者写作：
$$
19981 = 10 \times 1998 + 1
$$
结论：验证通过，余数为 1。
最终答案：53 关于模 1998 的乘法逆元是 377。
📖 相关资源
- cryptography - 密码学基础
- iot-network-security-review - 物联网网络安全复习
- iot-network-security-review-solutions-3 - RSA 计算题解