Solving quadratic congruence equation in Mathematica

Question

In order to solve

   x^2 == 123456 mod 1299709 

in Mathematica I have used:

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

which yields the correct answer.

Question: Is Reduce the best way ( performance, elegance or otherwise ) to solve quadratic congruence equations?

Answer 1

Apparently you are seeking the Modulus option.

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

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

Quoting the documentation:

Modulus -> n
is an option that can be given in certain algebraic functions to specify that integers should be treated modulo n.

• Equations for Modulus can be given in Solve and related functions.

• Modulus appears as an option in Factor, PolynomialGCD and PolynomialLCM, as well as in linear algebra functions such as Inverse, LinearSolve and Det.

• Arithmetic is usually done over the full ring ℤ of integers; setting the option Modulus specifies that arithmetic should instead be done in the finite ring ℤ_n.

• The setting Modulus->0 specifies the full ring ℤ of integers.

• Some functions require that Modulus be set to a prime, or a power of a prime. ℤ_n is a finite field when n is prime.

Answer 2

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

Daniel Lichtblau