求解Mathematica中的二次同余方程

Question

为了解决

   x^2 == 123456 mod 1299709 

在Mathematica我使用过:

  Reduce[x^2 == 123456 + 1299709 k, {x, k}, Integers]

这产生了正确的答案.

问题:减少求解二次同余方程的最佳方法(性能,优雅或其他方法)？

Answer 1

显然你正在寻找Modulus选择.

Reduce[x^2 == 123456, x, Modulus -> 1299709]

(*Out[]=  x == 427784 || x == 871925 *)

引用文档:

模数 - > n
是一个可以在某些代数函数中给出的选项,用于指定整数应该以模n的形式处理.

• 模数的方程可以在Solve和相关函数中给出.

• 模数在Factor,PolynomialGCD和PolynomialLCM以及线性代数函数(如Inverse,LinearSolve和Det)中作为选项出现.

• 算术通常在整数的整数环上完成; 设置选项模指定算术应改为在有限环ℤ完成_ñ.

• 设置Modulus-> 0指定整数的完整环ℤ.

• 某些函数需要将模数设置为素数或素数的幂.ℤ _ñ为有限域时,n是素数.