Revision history [back]

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?