Elysia Tools
导航
Math & Numbers
用扩展欧几里得算法求 a⁻¹ mod m：给出 Bézout 系数 a·x + m·y = gcd(a, m) 与完整的前向系数表（每行满足 r = a·s + m·t），并用 a × a⁻¹ ≡ 1 (mod m) 回代验证。支持 RSA 量级的大数（可达 10⁵¹² 位数级输入）；gcd(a, m) ≠ 1 时明确报告逆元不存在。经典例：RSA 中 17⁻¹ mod 3120 = 2753。
执行
填写表单、运行工具，并在同一页面查看结果。
案例
相关内容
工具使用指南
模逆元计算器利用扩展欧几里得算法快速求解 a⁻¹ mod m，并输出 Bézout 等式系数与完整递推推导步骤。工具支持 RSA 级别的大数运算（最高可达 10⁵¹² 位），能自动检验最大公约数 gcd(a, m)，在逆元不存在时给出明确提示，并通过回代等式验证计算结果的准确性。
背景
正在完成 RSA 算法作业，已知公钥指数 e = 17，模数欧拉函数 φ(n) = 3120，需要计算私钥指数 d 并展示推导过程。
问题
需要求出 17⁻¹ mod 3120 的值，并列出完整的扩展欧几里得递推步骤以写入实验报告。
如何使用
在数值 a 中填入 17，在模数 m 中填入 3120，输出样式选择“显示扩展欧几里得步骤”。
{"a": "17", "m": "3120", "style": "steps"}结果
得出私钥指数 2753，显示 Bézout 等式 17 × (-367) + 3120 × 2 = 1 及完整的步骤表，并验证 17 × 2753 ≡ 1 (mod 3120)。
背景
在解密一道仿射密码题目时，已知加密乘法密钥 a = 7，字母表模数 m = 26，需要找到解密所用的模逆元。
问题
需要快速获取 7⁻¹ mod 26 的数值以还原明文。
如何使用
在数值 a 中输入 7，在模数 m 中输入 26，输出样式选择“结果与验证”。
{"a": "7", "m": "26", "style": "result"}结果
快速得到逆元 15，并显示验证等式 7 × 15 = 105 = 4 × 26 + 1。
当且仅当 a 与模数 m 互质（即 gcd(a, m) = 1）时，模逆元才存在。
工具会自动先将负数 a 对 m 进行模运算化简为正整数，然后再求解逆元。
它是形如 a·x + m·y = gcd(a, m) 的线性等式，其中整数 x 在模 m 下即对应 a 的乘法逆元。
支持大整数运算，可处理高达 10⁵¹² 位数级别的 RSA 超大模数和数值。
因为输入的 a 与模数 m 存在大于 1 的公约数，无法通过模乘法得到余数 1。