Sage: Ticket #7931: Improved nth root for finite fields and integer_mods
https://trac.sagemath.org/ticket/7931
<p>
Implements an algorithm described in
</p>
<pre class="wiki">Johnston, Anna M. A generalized qth root algorithm.
Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms.
Baltimore, 1999: pp 929-930.
</pre><p>
This means we can take nth roots with large n, since we no longer need to create the polynomial x<sup>n</sup> - a.
</p>
en-usSagehttps://trac.sagemath.org/chrome/site/logo_sagemath_trac.png
https://trac.sagemath.org/ticket/7931
Trac 1.1.6roedThu, 14 Jan 2010 15:30:02 GMTattachment set
https://trac.sagemath.org/ticket/7931
https://trac.sagemath.org/ticket/7931
<ul>
<li><strong>attachment</strong>
set to <em>7931.patch</em>
</li>
</ul>
TicketroedThu, 14 Jan 2010 15:30:14 GMTstatus, description changed
https://trac.sagemath.org/ticket/7931#comment:1
https://trac.sagemath.org/ticket/7931#comment:1
<ul>
<li><strong>status</strong>
changed from <em>new</em> to <em>needs_review</em>
</li>
<li><strong>description</strong>
modified (<a href="/ticket/7931?action=diff&version=1">diff</a>)
</li>
</ul>
TicketrishiThu, 21 Jan 2010 17:09:24 GMT
https://trac.sagemath.org/ticket/7931#comment:2
https://trac.sagemath.org/ticket/7931#comment:2
<p>
Is there something I am missing?
</p>
<pre class="wiki">sage: K = GF(31)
sage: b=K(22)^200
sage: b.nth_root(200)
---------------------------------------------------------------------------
ValueError Traceback (most recent call last)
/virtual/scratch/rishi/sage-4.3.1.alpha2-sage.math.washington.edu-x86_64-Linux/<ipython console> in <module>()
/virtual/scratch/rishi/sage-4.3.1.alpha2-sage.math.washington.edu-x86_64-Linux/local/lib/python2.6/site-packages/sage/rings/integer_mod.so in sage.rings.integer_mod.IntegerMod_abstract.nth_root (sage/rings/integer_mod.c:11446)()
ValueError: no nth root
sage:
</pre>
TicketcremonaSun, 24 Jan 2010 18:46:58 GMT
https://trac.sagemath.org/ticket/7931#comment:3
https://trac.sagemath.org/ticket/7931#comment:3
<p>
It looks to me as if the original code (now deleted) worked with finite field elements, while thie new code works with integer-mods. That must surely mean that for non-prime finite fields there was something which worked, but now there isn't? If I am right, it would be a good idea to allow the original code as a fall-back.
</p>
TicketcremonaSun, 24 Jan 2010 18:54:53 GMTstatus changed
https://trac.sagemath.org/ticket/7931#comment:4
https://trac.sagemath.org/ticket/7931#comment:4
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>needs_work</em>
</li>
</ul>
<p>
Patch applies fine to 4.3.1 and tests pass, but I reproduced the example from rishi, so -- "needs work".
</p>
TicketroedTue, 23 Feb 2010 15:30:11 GMTattachment set
https://trac.sagemath.org/ticket/7931
https://trac.sagemath.org/ticket/7931
<ul>
<li><strong>attachment</strong>
set to <em>7931_nth_root.patch</em>
</li>
</ul>
<p>
Should fix the problem observed earlier
</p>
TicketroedTue, 23 Feb 2010 15:30:38 GMTstatus changed
https://trac.sagemath.org/ticket/7931#comment:5
https://trac.sagemath.org/ticket/7931#comment:5
<ul>
<li><strong>status</strong>
changed from <em>needs_work</em> to <em>needs_review</em>
</li>
</ul>
TicketzimmermaThu, 25 Feb 2010 22:29:00 GMTstatus changed
https://trac.sagemath.org/ticket/7931#comment:6
https://trac.sagemath.org/ticket/7931#comment:6
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>needs_info</em>
</li>
</ul>
<p>
David, should the 2nd patch be applied after the 1st one or alone?
</p>
TicketroedThu, 25 Feb 2010 23:46:33 GMTstatus changed
https://trac.sagemath.org/ticket/7931#comment:7
https://trac.sagemath.org/ticket/7931#comment:7
<ul>
<li><strong>status</strong>
changed from <em>needs_info</em> to <em>needs_review</em>
</li>
</ul>
<p>
Alone. Sorry about that.
</p>
TicketroedThu, 25 Feb 2010 23:49:27 GMTowner changed
https://trac.sagemath.org/ticket/7931#comment:8
https://trac.sagemath.org/ticket/7931#comment:8
<ul>
<li><strong>owner</strong>
changed from <em>AlexGhitza</em> to <em>roed</em>
</li>
</ul>
<p>
Oops. I made it depend on a bunch of other changes
</p>
<pre class="wiki">8218 -> 8332 -> 7880 -> 7883 -> 8333 -> 8334 -> this patch
</pre><p>
The actual change is fairly small; I'll try to extract it out and get something based only on 4.3.3, but I won't be able to do that tonight.
</p>
TicketzimmermaFri, 26 Feb 2010 08:21:12 GMT
https://trac.sagemath.org/ticket/7931#comment:9
https://trac.sagemath.org/ticket/7931#comment:9
<blockquote class="citation">
<p>
The actual change is fairly small; I'll try to extract it out and get something based only on 4.3.3, but I won't be able to do that tonight.
</p>
</blockquote>
<p>
that would be nice. Otherwise we can wait for the other patches to be reviewed.
Paul
</p>
TicketAlexGhitzaSat, 05 Jun 2010 00:19:44 GMT
https://trac.sagemath.org/ticket/7931#comment:10
https://trac.sagemath.org/ticket/7931#comment:10
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/7931#comment:8" title="Comment 8">roed</a>:
</p>
<blockquote class="citation">
<p>
Oops. I made it depend on a bunch of other changes
</p>
<pre class="wiki">8218 -> 8332 -> 7880 -> 7883 -> 8333 -> 8334 -> this patch
</pre><p>
The actual change is fairly small; I'll try to extract it out and get something based only on 4.3.3, but I won't be able to do that tonight.
</p>
</blockquote>
<p>
Just so we have trac's help to see which of the dependencies have already been merged: this depends on <a class="closed ticket" href="https://trac.sagemath.org/ticket/8218" title="enhancement: Finite Field move (closed: fixed)">#8218</a>, <a class="closed ticket" href="https://trac.sagemath.org/ticket/8332" title="enhancement: Changes FiniteField_givaro to Python (closed: fixed)">#8332</a>, <a class="closed ticket" href="https://trac.sagemath.org/ticket/7880" title="enhancement: Category of sets with partial maps. (closed: fixed)">#7880</a>, <a class="closed ticket" href="https://trac.sagemath.org/ticket/7883" title="enhancement: Added some functionality to ideals (closed: fixed)">#7883</a>, <a class="closed ticket" href="https://trac.sagemath.org/ticket/8333" title="enhancement: Finite fields to new coercion model (closed: duplicate)">#8333</a>, <a class="closed ticket" href="https://trac.sagemath.org/ticket/8334" title="enhancement: Improvements to residue fields (closed: fixed)">#8334</a>.
</p>
TicketdavidloefflerMon, 27 Sep 2010 10:13:59 GMT
https://trac.sagemath.org/ticket/7931#comment:11
https://trac.sagemath.org/ticket/7931#comment:11
<p>
Patch <code>7931_nth_root.patch</code> applies and builds fine and all doctests in <code>finite_rings</code> pass (with the dependencies installed); but I'm not terribly happy about the amount of code duplication that's going on -- the code added to <code>element_base</code> and <code>integer_mod</code> has about 30 lines that are virtually identical. Could it not be refactored to avoid this?
</p>
TicketroedMon, 27 Sep 2010 17:27:19 GMT
https://trac.sagemath.org/ticket/7931#comment:12
https://trac.sagemath.org/ticket/7931#comment:12
<p>
I completely agree. In the long run I want to change <code>FiniteFieldElement</code> to <code>FiniteRingElement</code> and make <code>IntegerMod_abstract</code> inherit from that. The <code>nth_root</code> function on <code>FiniteRingElement</code> can then be modified to handle both cases. An additional benefit of having such a common parent is that the finite field elements can then no longer require <code>p</code> prime (or <code>modulus</code> irreducible for that matter), which will be useful for p-adic extensions. In fact, I want to modify the finite field element classes to use templates (a la <code>sage.rings.polynomial.polynomial_template</code>): then we can share common code between polynomials, finite fields and rings, and p-adic extension fields. Coercions between them will be much easier and faster and it will make implementing extensions of extensions easier (which are necessary for p-adic extensions that are neither unramified nor totally ramified).
</p>
<p>
The first step though, of making <code>IntegerMod_abstract</code> inherit from <code>FiniteRingElement</code> caused compile-time bugs that I couldn't figure out and I gave up for the moment.
</p>
<p>
So currently their closest common superclass is <code>CommutativeRingElement</code>. It didn't seem like a good idea to put the common <code>nth_root</code> code there, and there wasn't another obvious way to do it. Any suggestions?
</p>
TicketroedMon, 27 Sep 2010 17:33:23 GMT
https://trac.sagemath.org/ticket/7931#comment:13
https://trac.sagemath.org/ticket/7931#comment:13
<p>
Another problem with the current patch is that for large <code>n</code>, finding the factorization of the size of the unit group becomes a bottleneck. There's a change in <a class="closed ticket" href="https://trac.sagemath.org/ticket/8335" title="enhancement: Finite field lattices via Conway polynomials (closed: fixed)">#8335</a> that helps with this problem for finite fields of small characteristic by caching the factorization of p<sup>n</sup>-1 and using the Cunningham package at <a class="needs_work ticket" href="https://trac.sagemath.org/ticket/7240" title="enhancement: factorization of Cunningham numbers - applications (needs_work)">#7240</a> to speed up the computation in the first place. Thematically it would make sense to backport it to this patch (which I've done already locally), but it makes this patch depend on <a class="needs_work ticket" href="https://trac.sagemath.org/ticket/7240" title="enhancement: factorization of Cunningham numbers - applications (needs_work)">#7240</a> (otherwise there are warnings printed when <code>_factor_cunningham</code> is used). What do you think?
</p>
TicketdavidloefflerMon, 27 Sep 2010 17:43:19 GMT
https://trac.sagemath.org/ticket/7931#comment:14
https://trac.sagemath.org/ticket/7931#comment:14
<p>
Could one perhaps have an auxilliary helper function (not a class method) that both of the nth root methods call? This is not terribly elegant, but it solves the duplication issue.
</p>
<p>
I'd argue for not making this patch depend on <a class="needs_work ticket" href="https://trac.sagemath.org/ticket/7240" title="enhancement: factorization of Cunningham numbers - applications (needs_work)">#7240</a>, since that patch seems to be stalled at the moment.
</p>
TicketroedTue, 28 Sep 2010 08:33:15 GMTattachment set
https://trac.sagemath.org/ticket/7931
https://trac.sagemath.org/ticket/7931
<ul>
<li><strong>attachment</strong>
set to <em>7931_nth_root.2.patch</em>
</li>
</ul>
<p>
Apply just this patch
</p>
TicketroedTue, 28 Sep 2010 08:34:14 GMT
https://trac.sagemath.org/ticket/7931#comment:15
https://trac.sagemath.org/ticket/7931#comment:15
<p>
I factored out most of the common code, and backported a few changes from <a class="closed ticket" href="https://trac.sagemath.org/ticket/8335" title="enhancement: Finite field lattices via Conway polynomials (closed: fixed)">#8335</a>. It still doesn't depend on <a class="needs_work ticket" href="https://trac.sagemath.org/ticket/7240" title="enhancement: factorization of Cunningham numbers - applications (needs_work)">#7240</a>.
</p>
TicketroedWed, 29 Sep 2010 01:53:24 GMTattachment set
https://trac.sagemath.org/ticket/7931
https://trac.sagemath.org/ticket/7931
<ul>
<li><strong>attachment</strong>
set to <em>7931_common_superclass.patch</em>
</li>
</ul>
<p>
Apply on top of 7931_nth_root.2.patch; moves _nth_root_common to <a class="missing wiki">FiniteRingElement?</a>, a new superclass of IntegerMod_abstract and the finite field elements
</p>
TicketzimmermaWed, 29 Sep 2010 08:57:33 GMTstatus changed; reviewer set
https://trac.sagemath.org/ticket/7931#comment:16
https://trac.sagemath.org/ticket/7931#comment:16
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>needs_info</em>
</li>
<li><strong>reviewer</strong>
set to <em>Paul Zimmermann</em>
</li>
</ul>
<p>
I tried applying both patches in sage-4.6.alpha1, but got a failure when running sage -br:
</p>
<pre class="wiki">python `which cython` --embed-positions --directive cdivision=True -I/tmp/sage-4.6.alpha1/devel/sage-7931 -o sage/rings/finite_rings/element_ntl_gf2e.cpp sage/rings/finite_rings/element_ntl_gf2e.pyx
Error converting Pyrex file to C:
------------------------------------------------------------
...
if PY_TYPE_CHECK(e, int) \
or PY_TYPE_CHECK(e, long) or PY_TYPE_CHECK(e, Integer):
GF2E_conv_long(res.x,int(e))
return res
if PY_TYPE_CHECK(e, FiniteFieldElement) or \
^
------------------------------------------------------------
/tmp/sage-4.6.alpha1/devel/sage-7931/sage/rings/finite_rings/element_ntl_gf2e.pyx:515:46: undeclared name not builtin: FiniteFieldElement
Error running command, failed with status 256.
sage: There was an error installing modified sage library code.
</pre><p>
Which version was used to produce the patches?
</p>
<p>
Paul
</p>
TicketzimmermaWed, 29 Sep 2010 09:58:53 GMT
https://trac.sagemath.org/ticket/7931#comment:17
https://trac.sagemath.org/ticket/7931#comment:17
<p>
I realized that I should also apply the patches <a class="closed ticket" href="https://trac.sagemath.org/ticket/7883" title="enhancement: Added some functionality to ideals (closed: fixed)">#7883</a> and <a class="closed ticket" href="https://trac.sagemath.org/ticket/8334" title="enhancement: Improvements to residue fields (closed: fixed)">#8334</a>, which were included in
sage-4.6.alpha2, but were not yet in sage-4.6.alpha1. However after importing <a class="closed ticket" href="https://trac.sagemath.org/ticket/7883" title="enhancement: Added some functionality to ideals (closed: fixed)">#7883</a>
successfully in sage-4.6.alpha1, importing <a class="closed ticket" href="https://trac.sagemath.org/ticket/8334" title="enhancement: Improvements to residue fields (closed: fixed)">#8334</a> gives:
</p>
<pre class="wiki">sage: hg_sage.import_patch("/tmp/8333_8334_ALL-better_commit_string.patch")
cd "/tmp/sage-4.6.alpha1/devel/sage" && hg status
cd "/tmp/sage-4.6.alpha1/devel/sage" && hg status
cd "/tmp/sage-4.6.alpha1/devel/sage" && hg import "/tmp/8333_8334_ALL-better_commit_string.patch"
applying /tmp/8333_8334_ALL-better_commit_string.patch
patching file sage/rings/ideal_monoid.py
Hunk #1 succeeded at 90 with fuzz 2 (offset 0 lines).
patching file sage/rings/residue_field.pyx
Hunk #3 succeeded at 74 with fuzz 2 (offset 0 lines).
Hunk #15 FAILED at 624
1 out of 36 hunks FAILED -- saving rejects to file sage/rings/residue_field.pyx.rej
abort: patch failed to apply
</pre><p>
and I'm stuck there. Maybe I should wait that sage-4.6.alpha2 is out.
</p>
<p>
Paul
</p>
TicketdavidloefflerWed, 29 Sep 2010 10:10:19 GMTstatus changed
https://trac.sagemath.org/ticket/7931#comment:18
https://trac.sagemath.org/ticket/7931#comment:18
<ul>
<li><strong>status</strong>
changed from <em>needs_info</em> to <em>needs_review</em>
</li>
</ul>
<p>
Ticket <a class="closed ticket" href="https://trac.sagemath.org/ticket/8334" title="enhancement: Improvements to residue fields (closed: fixed)">#8334</a> has some other dependencies -- they are listed on that ticket (Jeroen's comment 24). With those installed the patch applies fine, and all doctests in sage/rings pass (I'm running a full ptestlong cycle now), so I'm putting this back to "needs_review".
</p>
<p>
By the way, Mitesh has a lovely script <a class="ext-link" href="http://sage.math.washington.edu/home/release/sage-4.6.alpha2/merger-4.6.alpha2"><span class="icon"></span>merger-4.6.alpha2</a>, which you can run on a clean 4.6.alpha1 build and it will download and apply all of the patches and spkgs so far merged.
</p>
TicketzimmermaWed, 29 Sep 2010 11:14:54 GMT
https://trac.sagemath.org/ticket/7931#comment:19
https://trac.sagemath.org/ticket/7931#comment:19
<p>
I tried Mitesh's script on my sage-4.6.alpha1 build (after sage -b main), then I applied the two
patches from that ticket, but I still get the same error as in comment 16.
</p>
<p>
Paul
</p>
TicketdavidloefflerWed, 29 Sep 2010 11:47:24 GMT
https://trac.sagemath.org/ticket/7931#comment:20
https://trac.sagemath.org/ticket/7931#comment:20
<p>
That's bizarre, because the patches apply and build fine for me.
</p>
TicketdavidloefflerWed, 29 Sep 2010 12:48:10 GMT
https://trac.sagemath.org/ticket/7931#comment:21
https://trac.sagemath.org/ticket/7931#comment:21
<p>
Actually I hadn't myself tried Mitesh's script when I posted above; I just did, and I couldn't get it to work either. But it should work if you install:
</p>
<pre class="wiki">9898_pari_decl.patch
9753.patch
9764_ideal_repr_new.patch
trac_7883-ideals-folded.patch
8333_8334_ALL-rebased_for_9764.patch
7931_nth_root.2.patch
7931_common_superclass.patch
</pre>
TicketzimmermaWed, 29 Sep 2010 14:06:19 GMTstatus changed
https://trac.sagemath.org/ticket/7931#comment:22
https://trac.sagemath.org/ticket/7931#comment:22
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>needs_work</em>
</li>
</ul>
<p>
I managed to apply the patches following comment 21, however the following seems incorrect to me:
</p>
<pre class="wiki">sage: b=Integers(3)(2)
sage: b.nth_root(2)
1
</pre><p>
whereas in say Sage 4.4.4 we got <code>ValueError: no nth root</code>.
</p>
<p>
PS: I used the following reviewer program. Feel free to add it to the doctests.
</p>
<pre class="wiki">for n in range(2,100):
K=Integers(n)
for e in range(1,100):
for a in range(1,n):
b = K(a)
r = b.nth_root(e)
if r^e <> b:
print n, e, a
raise ValueError
</pre>
TicketroedThu, 30 Sep 2010 00:57:13 GMTstatus changed
https://trac.sagemath.org/ticket/7931#comment:23
https://trac.sagemath.org/ticket/7931#comment:23
<ul>
<li><strong>status</strong>
changed from <em>needs_work</em> to <em>needs_review</em>
</li>
</ul>
<p>
Thanks for catching that. I've fixed the problem and added a <code>_nth_root_naive</code> and check that the output of <code>b.nth_root(e, all=True)</code> matches <code>b._nth_root_naive(e)</code> for all <code>b</code> in <code>Zmod(n)</code> for <code>2 <= n < 100</code> and <code>1 <= e < 100</code>. A shortened version of this test is left in as a doctest for <code>_nth_root_naive</code>.
</p>
TicketroedThu, 30 Sep 2010 03:10:46 GMTattachment set
https://trac.sagemath.org/ticket/7931
https://trac.sagemath.org/ticket/7931
<ul>
<li><strong>attachment</strong>
set to <em>7931_fixes.patch</em>
</li>
</ul>
<p>
Apply on top of 7931_nth_root.2.patch and 7931_common_superclass.patch
</p>
TicketzimmermaThu, 30 Sep 2010 08:19:44 GMTstatus changed
https://trac.sagemath.org/ticket/7931#comment:24
https://trac.sagemath.org/ticket/7931#comment:24
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>needs_work</em>
</li>
</ul>
<p>
with the new patch, I still get unexpected results:
</p>
<pre class="wiki">sage: K=Integers(6)
sage: b=K(3)
sage: b.nth_root(0,all=True)
[3]
</pre><p>
Paul
</p>
TicketroedThu, 30 Sep 2010 09:19:26 GMTattachment set
https://trac.sagemath.org/ticket/7931
https://trac.sagemath.org/ticket/7931
<ul>
<li><strong>attachment</strong>
set to <em>7931_fix2.patch</em>
</li>
</ul>
<p>
Apply on top of previous patches
</p>
TicketroedThu, 30 Sep 2010 09:22:47 GMTstatus changed
https://trac.sagemath.org/ticket/7931#comment:25
https://trac.sagemath.org/ticket/7931#comment:25
<ul>
<li><strong>status</strong>
changed from <em>needs_work</em> to <em>needs_review</em>
</li>
</ul>
<p>
Unexpected indeed. Thanks for checking all these corner cases that I neglected (though some of the earlier ones were bugs I should have found if I'd tested sufficiently).
</p>
<p>
In this case I'm not quite sure what the right output is: an empty list or a <a class="missing wiki">ZeroDivisionError?</a>? I've gone for the empty list, on the theory that <code>b.nth_root(e)</code> should return a list of all elements <code>a</code> with a<sup>e</sup>=b, and this makes sense even if <code>e=0</code>.
</p>
TicketcremonaThu, 30 Sep 2010 10:37:54 GMT
https://trac.sagemath.org/ticket/7931#comment:26
https://trac.sagemath.org/ticket/7931#comment:26
<p>
e=0 is a hard case since there are too many solutions -- do we want to return all a in the ring? or all invertible a?
</p>
<p>
Similarly, do we allow negative e, where b must be invertible and b.nth_root(e) == (1/b).nth_root(-e), with an error if b is not invertible?
</p>
<p>
Or do we want to specify in the documentation that e must be positive, and raise an error if not?
</p>
TicketzimmermaThu, 30 Sep 2010 11:45:50 GMT
https://trac.sagemath.org/ticket/7931#comment:27
https://trac.sagemath.org/ticket/7931#comment:27
<p>
My 2 cents:
</p>
<ul><li>for e=0 and b<>1, b.nth_root(e) should return the empty list
</li></ul><ul><li>for e=0 and b=1, b.nth_root(e) should return only one solution, for example 1
(with all=True, return all a in the ring)
</li></ul><p>
Paul
</p>
TicketzimmermaThu, 30 Sep 2010 12:11:12 GMTstatus changed
https://trac.sagemath.org/ticket/7931#comment:28
https://trac.sagemath.org/ticket/7931#comment:28
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>needs_work</em>
</li>
</ul>
<p>
sorry, another problem:
</p>
<pre class="wiki">sage: n=13777831336991389951
sage: b=3798677550250515336
sage: e=10608321776141318019
sage: K = Integers(n)
sage: b=K(b)
sage: b.nth_root(e)
---------------------------------------------------------------------------
ZeroDivisionError Traceback (most recent call last)
</pre><p>
The documentation does not say when <code>ZeroDivisionError</code> can be obtained.
This was found with the following program:
</p>
<pre class="wiki">while True:
n = randint(0,2^64)
K = Integers(n)
b = K.random_element()
e = randint(0,2^64)
print n, b, e, a
sys.stdout.flush()
try:
a = b.nth_root(e)
if a^e <> b:
print n, b, e, a
raise NotImplementedError
except ValueError:
n = 0
</pre>
TicketroedFri, 01 Oct 2010 06:14:33 GMTstatus changed
https://trac.sagemath.org/ticket/7931#comment:29
https://trac.sagemath.org/ticket/7931#comment:29
<ul>
<li><strong>status</strong>
changed from <em>needs_work</em> to <em>needs_review</em>
</li>
</ul>
<p>
You've found a bug in crt: it claims to work as long as the moduli are relatively prime, but in fact would often fail if one of them was 1. I fixed that and clarified the behavior of <code>nth_root</code> when <code>n<=0</code> (it either returns the empty list or raises a <code>ValueError</code>, depending on the value of <code>all</code>; <code>mod(1,n).nth_root(0)</code> returns the list of all nonzero elements modulo n).
</p>
TicketzimmermaFri, 01 Oct 2010 12:05:04 GMTstatus changed
https://trac.sagemath.org/ticket/7931#comment:30
https://trac.sagemath.org/ticket/7931#comment:30
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>needs_work</em>
</li>
</ul>
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/7931#comment:29" title="Comment 29">roed</a>:
</p>
<blockquote class="citation">
<p>
You've found a bug in crt: it claims to work as long as the moduli are relatively prime, but in fact would often fail if one of them was 1. I fixed that and clarified the behavior of <code>nth_root</code> when <code>n<=0</code> (it either returns the empty list or raises a <code>ValueError</code>, depending on the value of <code>all</code>; <code>mod(1,n).nth_root(0)</code> returns the list of all nonzero elements modulo n).
</p>
</blockquote>
<p>
Hi David,
</p>
<p>
I'm not very happy with that answer. If a bug in crt was found, I would expect you to show a
concrete example, to report it as a new ticket, and to mention in your 3rd patch that it depends
on the new ticket, and can be removed once the new ticket is fixed.
</p>
<p>
Paul
</p>
TicketroedFri, 01 Oct 2010 14:28:50 GMTattachment set
https://trac.sagemath.org/ticket/7931
https://trac.sagemath.org/ticket/7931
<ul>
<li><strong>attachment</strong>
set to <em>7931_fix3.patch</em>
</li>
</ul>
<p>
Apply on top of previous patches
</p>
TicketroedFri, 01 Oct 2010 14:33:56 GMTstatus changed
https://trac.sagemath.org/ticket/7931#comment:31
https://trac.sagemath.org/ticket/7931#comment:31
<ul>
<li><strong>status</strong>
changed from <em>needs_work</em> to <em>needs_review</em>
</li>
</ul>
<p>
You're right that it needs doctests; I've added some. I also changed <code>7931_fix3.patch</code> by updating the <code>nth_root</code> function in <code>element_base</code> to match the behavior of the one in <code>integer_mod</code> for non-positive inputs.
</p>
<p>
Personally, I don't think that the crt bug is a major enough problem to need it's own ticket. It only applies if one of the arguments is mod(0,1). But I've separated the fix into its own patch; if you think it needs it's own ticket would you be willing to make the ticket and move the patch over there?
</p>
TicketzimmermaFri, 01 Oct 2010 15:18:54 GMTstatus changed; cc set
https://trac.sagemath.org/ticket/7931#comment:32
https://trac.sagemath.org/ticket/7931#comment:32
<ul>
<li><strong>cc</strong>
<em>robertwb</em> added
</li>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>needs_info</em>
</li>
</ul>
<p>
I don't understand the crt patch: the examples given already worked in 4.6.alpha1 (and
similarly in 4.4.4):
</p>
<pre class="wiki">----------------------------------------------------------------------
| Sage Version 4.6.alpha1, Release Date: 2010-09-18 |
| Type notebook() for the GUI, and license() for information. |
----------------------------------------------------------------------
**********************************************************************
* *
* Warning: this is a prerelease version, and it may be unstable. *
* *
**********************************************************************
sage: mod(0,1).crt(mod(4,17))
4
sage: mod(0,1).crt(mod(0,1))
0
sage: mod(21,22).crt(mod(0,1))
21
</pre><p>
What is exactly the crt bug (if any)?
</p>
<p>
Paul
</p>
TicketroedFri, 01 Oct 2010 15:49:06 GMTstatus changed
https://trac.sagemath.org/ticket/7931#comment:33
https://trac.sagemath.org/ticket/7931#comment:33
<ul>
<li><strong>status</strong>
changed from <em>needs_info</em> to <em>needs_review</em>
</li>
</ul>
<p>
Ah. Now I understand why this problem only appeared with your latest test program that used large moduli. The issue only occurs for <code>mod(0,1).crt(a)</code> when <code>a</code> has type <code>IntegerMod_gmp</code>. So we didn't see it for smaller moduli.
</p>
<p>
I've updated <code>7931_crt.patch</code>, and the doctest there does fail on my unpatched <code>4.6.alpha1</code>.
</p>
TicketzimmermaFri, 01 Oct 2010 15:56:28 GMT
https://trac.sagemath.org/ticket/7931#comment:34
https://trac.sagemath.org/ticket/7931#comment:34
<p>
I understand now, this is really a bug, and I think it should be considered in a separate ticket:
</p>
<pre class="wiki">sage: mod(0,1).crt(mod(4,2^31-2))
4
sage: mod(0,1).crt(mod(4,2^31-1))
---------------------------------------------------------------------------
ZeroDivisionError Traceback (most recent call last)
</pre>
TicketroedFri, 01 Oct 2010 16:05:30 GMT
https://trac.sagemath.org/ticket/7931#comment:35
https://trac.sagemath.org/ticket/7931#comment:35
<p>
This is now <a class="closed ticket" href="https://trac.sagemath.org/ticket/10047" title="defect: ZeroDivisionError in crt method of IntegerMod (closed: fixed)">#10047</a>.
</p>
TicketroedFri, 01 Oct 2010 16:06:49 GMTattachment set
https://trac.sagemath.org/ticket/7931
https://trac.sagemath.org/ticket/7931
<ul>
<li><strong>attachment</strong>
set to <em>7931_crt.patch</em>
</li>
</ul>
<p>
This is now <a class="closed ticket" href="https://trac.sagemath.org/ticket/10047" title="defect: ZeroDivisionError in crt method of IntegerMod (closed: fixed)">#10047</a>.
</p>
TicketdavidloefflerWed, 19 Jan 2011 16:31:29 GMTattachment set
https://trac.sagemath.org/ticket/7931
https://trac.sagemath.org/ticket/7931
<ul>
<li><strong>attachment</strong>
set to <em>7931_nth_root-folded.patch</em>
</li>
</ul>
<p>
Qfolded patch. Apply only this patch.
</p>
TicketdavidloefflerWed, 19 Jan 2011 16:33:25 GMT
https://trac.sagemath.org/ticket/7931#comment:36
https://trac.sagemath.org/ticket/7931#comment:36
<p>
It took me some while to understand what patches to apply in what order, so having done so I thought it might be helpful to qfold everything into one patch. (I'm pleasantly surprised that patchbot understood immediately.)
</p>
<p>
Now I'll have a look at the code.
</p>
TicketdavidloefflerWed, 19 Jan 2011 17:22:34 GMT
https://trac.sagemath.org/ticket/7931#comment:37
https://trac.sagemath.org/ticket/7931#comment:37
<p>
The code looks plausible, and I'm pleased to report that we aren't going to have the same problem as <a class="closed ticket" href="https://trac.sagemath.org/ticket/9304" title="defect: trac #8218 (finite_rings) broke all my pickles! (closed: fixed)">#9304</a> -- old pickled objects seem to unpickle just fine. I'm not qualified to comment on the details of the algorithm though. Paul?
</p>
TicketzimmermaThu, 20 Jan 2011 07:08:56 GMT
https://trac.sagemath.org/ticket/7931#comment:38
https://trac.sagemath.org/ticket/7931#comment:38
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/7931#comment:37" title="Comment 37">davidloeffler</a>:
</p>
<blockquote class="citation">
<p>
The code looks plausible, and I'm pleased to report that we aren't going to have the same problem as <a class="closed ticket" href="https://trac.sagemath.org/ticket/9304" title="defect: trac #8218 (finite_rings) broke all my pickles! (closed: fixed)">#9304</a> -- old pickled objects seem to unpickle just fine. I'm not qualified to comment on the details of the algorithm though. Paul?
</p>
</blockquote>
<p>
I won't have much time in the near future to look closely at the algorithm. Unless someone else
has time before me (John?) I'll look at this later. Don't hesitate to ping me.
</p>
<p>
Paul
</p>
TicketdavidloefflerTue, 25 Jan 2011 13:56:57 GMTattachment set
https://trac.sagemath.org/ticket/7931
https://trac.sagemath.org/ticket/7931
<ul>
<li><strong>attachment</strong>
set to <em>7931_nth_root-folded.2.patch</em>
</li>
</ul>
<p>
Fixed ReST formatting
</p>
TicketdavidloefflerTue, 25 Jan 2011 14:04:36 GMTstatus, reviewer changed
https://trac.sagemath.org/ticket/7931#comment:39
https://trac.sagemath.org/ticket/7931#comment:39
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>positive_review</em>
</li>
<li><strong>reviewer</strong>
changed from <em>Paul Zimmermann</em> to <em>Paul Zimmermann, David Loeffler, Bill Hart</em>
</li>
</ul>
<p>
I checked this one with Bill Hart, who knows much more about these things than I, and he reckons that the implementation looks correct; I've run the tests and it seems to be fine. My only contribution has been to qfold everything and adjust some of the reference manual formatting, so I guess that doesn't need a separate review.
</p>
<p>
Apply only the last patch.
</p>
TicketroedTue, 25 Jan 2011 17:05:19 GMT
https://trac.sagemath.org/ticket/7931#comment:40
https://trac.sagemath.org/ticket/7931#comment:40
<p>
Great! Thanks to all of the reviewers for looking at this.
</p>
TicketjdemeyerMon, 07 Feb 2011 08:14:22 GMTstatus changed; resolution, merged set
https://trac.sagemath.org/ticket/7931#comment:41
https://trac.sagemath.org/ticket/7931#comment:41
<ul>
<li><strong>status</strong>
changed from <em>positive_review</em> to <em>closed</em>
</li>
<li><strong>resolution</strong>
set to <em>fixed</em>
</li>
<li><strong>merged</strong>
set to <em>sage-4.6.2.alpha4</em>
</li>
</ul>
Ticket