1. 快速幂取模计算
密码学课程学生背景
正在完成关于 RSA 加密原理的作业,需要手动模拟小模数下的指数运算并写出推导过程。
问题
计算 17⁵ mod 13,并给出平方-乘法法的二进制拆解步骤。
如何使用
在操作中选择“快速幂”,输入 a = 17,b = 5,m = 13,点击运行。
结果
输出指数 5 = 101₂ 的二进制位拆分,得到 a^(2^0) ≡ 4 和 a^(2^2) ≡ 9,乘积约简后得出最终结果 10。
Elysia Tools
导航
Math & Numbers
在模 m 下做加、减、乘、逆元与快速幂运算,全部使用 BigInt 精确计算(数值可达 10¹⁸)。加、减、乘给出逐步约简过程并输出 [0, m−1] 上的规范代表;逆元用扩展欧几里得算法求 a⁻¹ mod m,gcd(a, m) ≠ 1 时明确报告不存在;快速幂展示平方-乘法表中指数二进制分解的每个数位。经典例:17⁵ mod 13 = 10;5⁻¹ mod 18 = 11。
执行
填写表单、运行工具,并在同一页面查看结果。
案例
相关内容
工具使用指南
模运算计算器支持在给定模数 m 下进行精确的加法、减法、乘法、模逆元以及快速幂运算。工具基于 BigInt 构建,支持高达 10¹⁸ 的大数运算,不仅提供最终的规范余数([0, m−1] 区间),还会完整呈现扩展欧几里得算法的贝祖等式过程以及快速幂的二进制平方-乘法拆解步骤。
背景
正在完成关于 RSA 加密原理的作业,需要手动模拟小模数下的指数运算并写出推导过程。
问题
计算 17⁵ mod 13,并给出平方-乘法法的二进制拆解步骤。
如何使用
在操作中选择“快速幂”,输入 a = 17,b = 5,m = 13,点击运行。
结果
输出指数 5 = 101₂ 的二进制位拆分,得到 a^(2^0) ≡ 4 和 a^(2^2) ≡ 9,乘积约简后得出最终结果 10。
背景
在编写组合数学计数程序时,需要计算除法取模,即寻找某个数在模 18 下的乘法逆元。
问题
判断 5 在模 18 下是否存在逆元,若存在则求出最小非负整数解。
如何使用
在操作中选择“逆元”,输入 a = 5,m = 18,无需输入 b,点击运行。
结果
输出 Bézout 等式 5 × (-7) + 18 × 2 = 1,并验证给出 5⁻¹ ≡ 11 (mod 18)。
模逆元是满足 (a × x) ≡ 1 (mod m) 的整数 x。只有当 a 与模数 m 互质(即 gcd(a, m) = 1)时逆元才存在,否则工具会提示不存在。
快速幂利用指数的二进制分解与连续平方,将计算复杂度从 O(b) 降低到 O(log b),可在极短时间内完成超大指数的计算。
底层采用 BigInt 精确计算,支持高达 10¹⁸ 及以上的整数,避免了标准浮点数的精度溢出问题。
工具会自动加上模数 m 并取模,将结果转换到 [0, m−1] 的规范非负余数区间。
不需要。求逆元操作只需要输入被求逆的数值 a 和模数 m,数值 b 会被自动忽略。