Elysia Tools
导航
Math & Numbers
计算 Jacobi 符号 (a/n)（n 为奇数，可达 10¹⁸；素数时即 Legendre 符号）：素数模下 a^((n−1)/2) ≡ 1 判定为二次剩余，并用 Tonelli–Shanks（或 p ≡ 3 (mod 4) 时的直接公式）给出平方根 ±√a；符号为 −1 则 a 一定不是二次剩余。合数模下 Jacobi 符号只是必要条件：−1 证明非剩余，+1 不确定（n ≤ 10⁵ 时自动暴力枚举求真相）。经典例：10 是 mod 13 的二次剩余，根为 ±6。
执行
填写表单、运行工具，并在同一页面查看结果。
案例
相关内容
工具使用指南
二次剩余判定器用于计算奇数模下的 Jacobi 符号与 Legendre 符号，快速判定同余方程 x² ≡ a (mod n) 是否有解。在素数模下，工具结合欧拉判别法与 Tonelli–Shanks 算法直接求解模平方根；在合数模下支持符号性质检验与小模数枚举验证。
背景
正在实现 Rabin 加密算法的解密部分，需要验证模数 13 下 10 的模平方根。
问题
需要快速判定 x² ≡ 10 (mod 13) 是否有解并求出对应的解集合。
如何使用
在数值 a 输入 10，模数 n 输入 13，勾选“当 n 为素数时，求解 x² ≡ a (mod n)”。
结果
判定 10 是 mod 13 的二次剩余，Legendre 符号为 1，并由 Tonelli–Shanks 给出平方根 x = 6 与 x = 7。
背景
正在为学生演示 Jacobi 符号为 +1 但实际无解的经典合数反例。
问题
验证在模 15 下数值 2 的 Jacobi 符号及其真实剩余状态。
如何使用
在数值 a 输入 2，模数 n 输入 15，并启动求解检测。
结果
工具显示 Jacobi 符号 (2/15) = +1，并通过暴力枚举明确指出 x² ≡ 2 (mod 15) 无解，证明 2 不是二次剩余。
Legendre 符号仅适用于奇素数模，结果完全决定是否为二次剩余；Jacobi 符号推广到了任意正奇数模，结果为 -1 可确认非剩余，但结果为 +1 时在合数模下不保证一定有解。
模数 n 必须为奇数，支持范围在 3 到 10¹⁸ 之间。
合数模下 Jacobi 符号为 +1 属于未定状态；当 n ≤ 10⁵ 时，工具会自动通过穷举枚举确认是否存在真实的模平方根。
数值 a 支持大整数输入（最高可达 10⁵¹²），计算前会先自动取模规约至 [0, n-1] 区间。
它是一种用于求解奇素数模二次同余方程 x² ≡ a (mod p) 模平方根的高效多项式时间算法。