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:
- 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? - 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?
[EDIT: read second comment first!] There is an inconsistency I do not understand yet: The function
sqrtyou use simply calls the methodsqrton the value-Z(D)which is an element ofZmod(625)(that is, what you type is equivalent toZmod(625)(-84100).sqrt()). Actually, elements ofZmod(625)have not only the methodsqrtbut also a methodsquare_root. It is supposed to be the same thing (square_rootis defined as an alias forsqrt), but the two methods do not return the same result!I do not know where this can come!
Both answers make sense, since an element can have distinct square roots. And both $30^2$ and $280^2$ are equal to $-84100$ modulo $625$. The problem then reduces to how to define the or a square root in $\mathbb Z/625\mathbb Z$. You can obtain all the square roots using
Zmod(625)(-84100).sqrt(all = True)(or replacing withsquare_root, this time one obtains the same result) :[30, 95, 155, 220, 280, 345, 405, 470, 530, 595].The inconsistency I mentioned in my first comment concerns the difference between
sqrtandsquare_rootin SageMath.Quite interesting. Using
square_rootactually produced the result that I want. Thank you. If you can provide it as an answer, I can accept.OK, I found the origin of the inconsistency, I can write an answer!