Processing math: 14%

First time here? Check out the FAQ!

Ask Your Question

Revision history [back]

click to hide/show revision 1
initial version

answered 7 years ago

B r u n o gravatar image

Your computation asks for a square roots of 275 modulo 625 (since -84100 = 275\mod 625). There exist many such square roots (amongst which 30 and 280), as shown by the following computation:

sage: Zmod(625)(275).sqrt(all=True)
[30, 95, 155, 220, 280, 345, 405, 470, 530, 595]

Thus, the functions sqrt in Magma and SageMath both give sensible results. They simply do not make the same choice when they choose one of the possible square roots.

Note : There exist two implementations in SageMath for the computation of square roots in \mathbb Z/n\mathbb Z. One is specific for small values of n (32 bits) and the other for larger values of n. It happens that they do not to make the same choice for a square root. In your case, sqrt is the method for small values of n. But one can specifically call the other implementation using square_root.

The method for small values return the smallest (using the natural order on integers) square root, that is 30 in your case, using a brute force algorithm. The algorithm used for large values is based on Newton method.

Important remark: My explanation are specific to the value 625 which is a prime power, different from 3 modulo 4.

Questions for knowledgeable SageMath developers:

  1. The alias square_root = sqrt is defined in IntegerMod_abstract but not in IntegerMod_int, whence the different answers. Should it be defined also in IntegerMod_int for consistency?
  2. Is there a satisfactory way to define a preferred square root in \mathbb Z/625\mathbb Z, to ensure consistency between implementations, and to satisfy the principle of least surprise?