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:
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?