在 Mathematica 中求解二次同余方程

Question

为了在

   x^2 == 123456 mod 1299709 

Mathematica 中求解，我使用了：

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

这会产生正确的答案。

问题：Reduce 是解决二次同余方程的最佳方法（性能、优雅或其他）吗？

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 指定算术应该是
  在有限环 ℤ_n 中完成。

• 设置 Modulus->0 指定整环 ℤ 整数。

• 某些函数要求将模数设置为素数或素数的幂。当 n 为素数时，ℤ_n 是有限域。

Answer 2

In[1]:= PowerModList[123456, 1/2, 1299709]
Out[1]= {427784, 871925}

丹尼尔·利希布劳