ASKSAGE: Sage Q&A Forum - Individual question feedhttp://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Tue, 21 Nov 2017 07:40:31 -0600Inconsistent result between Sage and Magma for sqrthttp://ask.sagemath.org/question/39670/inconsistent-result-between-sage-and-magma-for-sqrt/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?Mon, 20 Nov 2017 08:57:39 -0600http://ask.sagemath.org/question/39670/inconsistent-result-between-sage-and-magma-for-sqrt/Comment by B r u n o for <p>I have the following Magma code:</p>
<pre><code>N2t := 625;
D := 84100;
tau:= Sqrt(-IntegerRing(N2t)!D);
tau
</code></pre>
<p>It basically creates a ring of integers modulo 625, evaluated it for the value of <code>D</code> with negation, and finally applies a square root calculation. Now, the result produced is <code>280</code>. When, I convert the code to Sage such as this:</p>
<pre><code>N2t = 625
D = 84100
Z = Integers(N2t)
tau = sqrt(-Z(D))
tau
</code></pre>
<p>I get a result of <code>30</code>. Any ideas why this is the case?</p>
http://ask.sagemath.org/question/39670/inconsistent-result-between-sage-and-magma-for-sqrt/?comment=39674#post-id-39674OK, I found the origin of the inconsistency, I can write an answer!Mon, 20 Nov 2017 10:10:20 -0600http://ask.sagemath.org/question/39670/inconsistent-result-between-sage-and-magma-for-sqrt/?comment=39674#post-id-39674Comment by whatever for <p>I have the following Magma code:</p>
<pre><code>N2t := 625;
D := 84100;
tau:= Sqrt(-IntegerRing(N2t)!D);
tau
</code></pre>
<p>It basically creates a ring of integers modulo 625, evaluated it for the value of <code>D</code> with negation, and finally applies a square root calculation. Now, the result produced is <code>280</code>. When, I convert the code to Sage such as this:</p>
<pre><code>N2t = 625
D = 84100
Z = Integers(N2t)
tau = sqrt(-Z(D))
tau
</code></pre>
<p>I get a result of <code>30</code>. Any ideas why this is the case?</p>
http://ask.sagemath.org/question/39670/inconsistent-result-between-sage-and-magma-for-sqrt/?comment=39673#post-id-39673Quite interesting. Using `square_root` actually produced the result that I want. Thank you. If you can provide it as an answer, I can accept.Mon, 20 Nov 2017 10:00:04 -0600http://ask.sagemath.org/question/39670/inconsistent-result-between-sage-and-magma-for-sqrt/?comment=39673#post-id-39673Comment by B r u n o for <p>I have the following Magma code:</p>
<pre><code>N2t := 625;
D := 84100;
tau:= Sqrt(-IntegerRing(N2t)!D);
tau
</code></pre>
<p>It basically creates a ring of integers modulo 625, evaluated it for the value of <code>D</code> with negation, and finally applies a square root calculation. Now, the result produced is <code>280</code>. When, I convert the code to Sage such as this:</p>
<pre><code>N2t = 625
D = 84100
Z = Integers(N2t)
tau = sqrt(-Z(D))
tau
</code></pre>
<p>I get a result of <code>30</code>. Any ideas why this is the case?</p>
http://ask.sagemath.org/question/39670/inconsistent-result-between-sage-and-magma-for-sqrt/?comment=39671#post-id-39671**[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!Mon, 20 Nov 2017 09:45:44 -0600http://ask.sagemath.org/question/39670/inconsistent-result-between-sage-and-magma-for-sqrt/?comment=39671#post-id-39671Comment by B r u n o for <p>I have the following Magma code:</p>
<pre><code>N2t := 625;
D := 84100;
tau:= Sqrt(-IntegerRing(N2t)!D);
tau
</code></pre>
<p>It basically creates a ring of integers modulo 625, evaluated it for the value of <code>D</code> with negation, and finally applies a square root calculation. Now, the result produced is <code>280</code>. When, I convert the code to Sage such as this:</p>
<pre><code>N2t = 625
D = 84100
Z = Integers(N2t)
tau = sqrt(-Z(D))
tau
</code></pre>
<p>I get a result of <code>30</code>. Any ideas why this is the case?</p>
http://ask.sagemath.org/question/39670/inconsistent-result-between-sage-and-magma-for-sqrt/?comment=39672#post-id-39672Both 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.Mon, 20 Nov 2017 09:51:49 -0600http://ask.sagemath.org/question/39670/inconsistent-result-between-sage-and-magma-for-sqrt/?comment=39672#post-id-39672Answer by B r u n o for <p>I have the following Magma code:</p>
<pre><code>N2t := 625;
D := 84100;
tau:= Sqrt(-IntegerRing(N2t)!D);
tau
</code></pre>
<p>It basically creates a ring of integers modulo 625, evaluated it for the value of <code>D</code> with negation, and finally applies a square root calculation. Now, the result produced is <code>280</code>. When, I convert the code to Sage such as this:</p>
<pre><code>N2t = 625
D = 84100
Z = Integers(N2t)
tau = sqrt(-Z(D))
tau
</code></pre>
<p>I get a result of <code>30</code>. Any ideas why this is the case?</p>
http://ask.sagemath.org/question/39670/inconsistent-result-between-sage-and-magma-for-sqrt/?answer=39675#post-id-39675Your 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?
1. 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*?Mon, 20 Nov 2017 10:35:37 -0600http://ask.sagemath.org/question/39670/inconsistent-result-between-sage-and-magma-for-sqrt/?answer=39675#post-id-39675Comment by B r u n o for <p>Your computation asks for <em>a</em> square roots of $275$ <em>modulo</em> $625$ (since $-84100 = 275\mod 625$). There exist many such square roots (amongst which $30$ and $280$), as shown by the following computation:</p>
<pre><code>sage: Zmod(625)(275).sqrt(all=True)
[30, 95, 155, 220, 280, 345, 405, 470, 530, 595]
</code></pre>
<p>Thus, the functions <code>sqrt</code> 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.</p>
<p><strong>Note</strong> : 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, <code>sqrt</code> is the method for small values of $n$. But one can specifically call the other implementation using <code>square_root</code>. </p>
<p>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. </p>
<p><strong>Important remark:</strong> My explanation are specific to the value $625$ which is a prime power, different from $3$ <em>modulo</em> $4$.</p>
<p><strong>Questions for knowledgeable SageMath developers:</strong> </p>
<ol>
<li>The alias <code>square_root = sqrt</code> is defined in <code>IntegerMod_abstract</code> but not in <code>IntegerMod_int</code>, whence the different answers. Should it be defined also in <code>IntegerMod_int</code> for consistency?</li>
<li>Is there a satisfactory way to define a <em>preferred</em> square root in $\mathbb Z/625\mathbb Z$, to ensure consistency between implementations, and to satisfy the <em>principle of least surprise</em>?</li>
</ol>
http://ask.sagemath.org/question/39670/inconsistent-result-between-sage-and-magma-for-sqrt/?comment=39696#post-id-39696I 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..Tue, 21 Nov 2017 07:40:31 -0600http://ask.sagemath.org/question/39670/inconsistent-result-between-sage-and-magma-for-sqrt/?comment=39696#post-id-39696Comment by whatever for <p>Your computation asks for <em>a</em> square roots of $275$ <em>modulo</em> $625$ (since $-84100 = 275\mod 625$). There exist many such square roots (amongst which $30$ and $280$), as shown by the following computation:</p>
<pre><code>sage: Zmod(625)(275).sqrt(all=True)
[30, 95, 155, 220, 280, 345, 405, 470, 530, 595]
</code></pre>
<p>Thus, the functions <code>sqrt</code> 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.</p>
<p><strong>Note</strong> : 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, <code>sqrt</code> is the method for small values of $n$. But one can specifically call the other implementation using <code>square_root</code>. </p>
<p>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. </p>
<p><strong>Important remark:</strong> My explanation are specific to the value $625$ which is a prime power, different from $3$ <em>modulo</em> $4$.</p>
<p><strong>Questions for knowledgeable SageMath developers:</strong> </p>
<ol>
<li>The alias <code>square_root = sqrt</code> is defined in <code>IntegerMod_abstract</code> but not in <code>IntegerMod_int</code>, whence the different answers. Should it be defined also in <code>IntegerMod_int</code> for consistency?</li>
<li>Is there a satisfactory way to define a <em>preferred</em> square root in $\mathbb Z/625\mathbb Z$, to ensure consistency between implementations, and to satisfy the <em>principle of least surprise</em>?</li>
</ol>
http://ask.sagemath.org/question/39670/inconsistent-result-between-sage-and-magma-for-sqrt/?comment=39693#post-id-39693Yes, 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*.Tue, 21 Nov 2017 05:17:20 -0600http://ask.sagemath.org/question/39670/inconsistent-result-between-sage-and-magma-for-sqrt/?comment=39693#post-id-39693Comment by B r u n o for <p>Your computation asks for <em>a</em> square roots of $275$ <em>modulo</em> $625$ (since $-84100 = 275\mod 625$). There exist many such square roots (amongst which $30$ and $280$), as shown by the following computation:</p>
<pre><code>sage: Zmod(625)(275).sqrt(all=True)
[30, 95, 155, 220, 280, 345, 405, 470, 530, 595]
</code></pre>
<p>Thus, the functions <code>sqrt</code> 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.</p>
<p><strong>Note</strong> : 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, <code>sqrt</code> is the method for small values of $n$. But one can specifically call the other implementation using <code>square_root</code>. </p>
<p>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. </p>
<p><strong>Important remark:</strong> My explanation are specific to the value $625$ which is a prime power, different from $3$ <em>modulo</em> $4$.</p>
<p><strong>Questions for knowledgeable SageMath developers:</strong> </p>
<ol>
<li>The alias <code>square_root = sqrt</code> is defined in <code>IntegerMod_abstract</code> but not in <code>IntegerMod_int</code>, whence the different answers. Should it be defined also in <code>IntegerMod_int</code> for consistency?</li>
<li>Is there a satisfactory way to define a <em>preferred</em> square root in $\mathbb Z/625\mathbb Z$, to ensure consistency between implementations, and to satisfy the <em>principle of least surprise</em>?</li>
</ol>
http://ask.sagemath.org/question/39670/inconsistent-result-between-sage-and-magma-for-sqrt/?comment=39692#post-id-39692Both Magma and SageMath return *a* square root, but do not pretend anything about which one is chosen there exist several of them. See [here](http://magma.maths.usyd.edu.au/magma/handbook/text/176#1422) for Magma and [there](http://doc.sagemath.org/html/en/reference/finite_rings/sage/rings/finite_rings/integer_mod.html#sage.rings.finite_rings.integer_mod.IntegerMod_int.sqrt) 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?Tue, 21 Nov 2017 04:56:54 -0600http://ask.sagemath.org/question/39670/inconsistent-result-between-sage-and-magma-for-sqrt/?comment=39692#post-id-39692Comment by whatever for <p>Your computation asks for <em>a</em> square roots of $275$ <em>modulo</em> $625$ (since $-84100 = 275\mod 625$). There exist many such square roots (amongst which $30$ and $280$), as shown by the following computation:</p>
<pre><code>sage: Zmod(625)(275).sqrt(all=True)
[30, 95, 155, 220, 280, 345, 405, 470, 530, 595]
</code></pre>
<p>Thus, the functions <code>sqrt</code> 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.</p>
<p><strong>Note</strong> : 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, <code>sqrt</code> is the method for small values of $n$. But one can specifically call the other implementation using <code>square_root</code>. </p>
<p>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. </p>
<p><strong>Important remark:</strong> My explanation are specific to the value $625$ which is a prime power, different from $3$ <em>modulo</em> $4$.</p>
<p><strong>Questions for knowledgeable SageMath developers:</strong> </p>
<ol>
<li>The alias <code>square_root = sqrt</code> is defined in <code>IntegerMod_abstract</code> but not in <code>IntegerMod_int</code>, whence the different answers. Should it be defined also in <code>IntegerMod_int</code> for consistency?</li>
<li>Is there a satisfactory way to define a <em>preferred</em> square root in $\mathbb Z/625\mathbb Z$, to ensure consistency between implementations, and to satisfy the <em>principle of least surprise</em>?</li>
</ol>
http://ask.sagemath.org/question/39670/inconsistent-result-between-sage-and-magma-for-sqrt/?comment=39676#post-id-39676Take 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`.Mon, 20 Nov 2017 12:05:02 -0600http://ask.sagemath.org/question/39670/inconsistent-result-between-sage-and-magma-for-sqrt/?comment=39676#post-id-39676