数学研发论坛

 找回密码
 欢迎注册
查看: 442|回复: 6

[求助] 求解 x^2 ≡ a (mod n)

[复制链接]
发表于 2023-1-5 09:34:08 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能,让你轻松玩转社区。

您需要 登录 才可以下载或查看,没有帐号?欢迎注册

x
本帖最后由 uk702 于 2023-1-5 12:51 编辑

当  n  为素数 p 时,华罗庚的《数论导引》中给出了如下的解答(下面用 (a, p) 表示勒让德符号 \( \left( \frac{a}{p} \right) \)):

1)若 \(p\equiv 3\pmod{4}\),由于有 (a, p) = 1,故 \( a^{\frac{p-1}{2}} \equiv 1 \pmod{p}\),∴  \( (a^{\frac{p+1}{4}})^2 \equiv a\pmod{p} \)
∴  \( a^{\frac{p+1}{4}} \) 为其解。
2)若 \(p\equiv 5\pmod{8}\),先求 a = -1 的解,由威尔逊定理,有 \( -1\equiv (p-1)! \equiv (1 \cdot 2 \cdot 3 ... \cdot \frac{p-1}{2})^2\equiv \left( \frac{p-1}{2}! \right)^2 \)
∴  \( (\frac{p-1}{2})! \) 是 \( x^2 \equiv -1 \pmod{p}\) 的解。
对于一般的 \( x^2 \equiv  a\pmod{p}\),由于有 (a, p) = 1,故 \( a^{\frac{p-1}{2}} \equiv 1\pmod{p}\),计算得 \( \left( a^{\frac{p+3}{8}} \cdot \frac{p-1}{2} ! \right)^2  \equiv a \pmod{p}\)
∴ \( a^{\frac{p+3}{8}} \cdot\left( \frac{p-1}{2} \right)! \)  是它的解。
3)若 \(p\equiv 1\pmod{8}\),书云无太好的解法,一般可采取逐步舍弃的方法,详见书。

http://www.numbertheory.org/calc/krm_calc.html,提供若干工具(函数),用以求解这类问题(和各种类型的二元二次丢番都不定方程),
如求解 x^2+3 ≡ 0 (mod 9999999967),可用 sqroot(-3, 9999999967, &a[]),解得 x=±831463263 。

另,如果用 MMA 或 Pari/GP,如何求解?我看了一下 guide/NumberTheory,还没找到明显的答案。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2023-1-5 10:08:29 | 显示全部楼层
  1. PowerModList[-3, 1/2, 9999999967]
复制代码
  1. Solve[x^2 + 3 == 0, Modulus -> 9999999967]
复制代码

点评

PowerModList[-3, 1/2, 9999999967]  发表于 2023-1-5 13:12
多谢老大!PowerMod 用于求解分数方幂,超出了我的想像。  发表于 2023-1-5 10:21
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2023-1-5 13:32:35 | 显示全部楼层

点评

好东西!多谢。我在西电的教材《数论算法》中也找到这样的算法。  发表于 2023-1-5 13:49
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2023-1-10 12:15:49 | 显示全部楼层
\(p\equiv3\pmod{4}\)和\(p\equiv1\pmod{4}\)两种类型进行,其中\(p\equiv1\pmod{4}\)见如下链接:
https://bbs.emath.ac.cn/forum.ph ... amp;page=1#pid78100
另见《数论经典著作系列:初等数论(3)》陈景润
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|数学研发网 ( 苏ICP备07505100号 )

GMT+8, 2023-1-30 06:44 , Processed in 0.117578 second(s), 17 queries .

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

快速回复 返回顶部 返回列表