Solving the quadratic congruence equation in Mathematica

Question

To solve

   x^2 == 123456 mod 1299709 

in Mathematica I used:

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

which gives the correct answer.

Question: Is Reducing the best way (performance, elegance or otherwise) for solving quadratic congruence equations?

Answer 1

Apparently you are looking Modulus.

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

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

Indication of documentation:

Module → n
is an option that can be specified in some algebraic functions to indicate that integers should be processed modulo 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}