1 | initial version |

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

Copyright Sage, 2010. Some rights reserved under creative commons license. Content on this site is licensed under a Creative Commons Attribution Share Alike 3.0 license.