Inconsistent result between Sage and Magma for sqrt

Anonymous

I have the following Magma code:

N2t := 625;
D := 84100;
tau:= Sqrt(-IntegerRing(N2t)!D);
tau

It basically creates a ring of integers modulo 625, evaluated it for the value of D with negation, and finally applies a square root calculation. Now, the result produced is 280. When, I convert the code to Sage such as this:

N2t = 625
D = 84100
Z = Integers(N2t)
tau = sqrt(-Z(D))
tau

I get a result of 30. Any ideas why this is the case?

Comments

[EDIT: read second comment first!] There is an inconsistency I do not understand yet: The function sqrt you use simply calls the method sqrt on the value -Z(D) which is an element of Zmod(625) (that is, what you type is equivalent to Zmod(625)(-84100).sqrt()). Actually, elements of Zmod(625) have not only the method sqrt but also a method square_root. It is supposed to be the same thing (square_root is defined as an alias for sqrt), but the two methods do not return the same result!

sage: Zmod(625)(-84100).sqrt()
30
sage: Zmod(625)(-84100).square_root()
280

I do not know where this can come!

B r u n o ( 7 years ago )

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 with square_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 sqrt and square_root in SageMath.

B r u n o ( 7 years ago )

Quite interesting. Using square_root actually produced the result that I want. Thank you. If you can provide it as an answer, I can accept.

whatever ( 7 years ago )

OK, I found the origin of the inconsistency, I can write an answer!

B r u n o ( 7 years ago )

add a comment

answered 7 years ago

B r u n o
1603 ●5 ●21 ●43

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?

link

Comments

Take this for example Zmod(23753)(-100), both sqrt and square_root return the same result, meaning the smallest valid value, that is 2244, whereas Magma returns 21509.

whatever ( 7 years ago )

Both Magma and SageMath return a square root, but do not pretend anything about which one is chosen there exist several of them. See here for Magma and there for SageMath. At least for SageMath you can read the code and the comments to deduce which square root is returned. You have absolutely no clue in Magma since it is a proprietary software.

Since both $2244^2$ and $21509^2$ both equal $-100$ modulo $23753$ , there is no problem in the fact that the two softwares answer differently!

The question: What do you assume on Magma's answer, that is not satisfied in SageMath?

B r u n o ( 7 years ago )

Yes, both return correct answers, no doubt about it. It was just that I was rewriting a Magma code in Sage, and I want to have consistency, and as you say satisfy the principle of least surprise.

whatever ( 7 years ago )

I understand your point. But I can see only two possibilities: Either your code needs some square root, and any of them is OK (thus SageMath's answer is satisfying). Or your code needs a specific square root, and you assume that Magma returns this specific root. In such case, notice that Magma does not guarantee anything about the square root it returns (so that your code is to the least fragile). And if you need a specific square root, it must be possible to find it using sqrt(all=True) and then to filter to find the required value. To be more precise, it is weird to have some code that depends on an undocumented behavior of Magma..

B r u n o ( 7 years ago )

add a comment

Inconsistent result between Sage and Magma for sqrt

Comments

1 Answer

Comments

Your Answer

Question Tools

Stats

Related questions

Inconsistent result between Sage and Magma for sqrt savecancel

Comments

1 Answer

Comments

Your Answer

Question Tools

Stats

Related questions

Inconsistent result between Sage and Magma for sqrt