如何在Pari/Gp中计算合数模数下的模平方根？

你使用sqrt(Mod(8225, 12707))报错，是因为Pari/gp的sqrt()函数仅支持模数为质数的场景，而12707是合数（分解为97 × 131），因此无法直接调用该函数。

正确语法 #

要在合数模下求解平方根，需使用Pari/gp内置的sqrtmod()函数，语法格式为：

sqrtmod(a, n)

参数说明：

• a：待开平方的整数
• n：模数（支持合数）

针对你的示例的执行结果 #

执行以下代码：

? sqrtmod(8225, 12707)
%1 = 0

返回0表示该方程无解，原因是：

• 计算8225 mod 97得到77，通过kronecker(77, 97)可验证77是模97的二次非剩余，因此不存在满足条件的平方根。

额外验证工具 #

若要提前判断一个数是否为模n的二次剩余，可使用kronecker()函数：

? kronecker(8225, 12707)
%1 = -1

返回值为-1时，说明该数是模n的二次非剩余，不存在平方根；返回1则说明存在平方根；返回0说明该数与模数不互质。

内容的提问来源于stack exchange，提问作者user2284570