Opened 8 years ago
Closed 8 years ago
#16162 closed defect (fixed)
CantorZassenhaus may enter infinite loop over GF(2**k) and cannot be interrupted
Reported by:  jpflori  Owned by:  

Priority:  critical  Milestone:  sage6.3 
Component:  finite rings  Keywords:  finite field polynomial root factor 
Cc:  defeo, pbruin, sbesnier  Merged in:  
Authors:  JeanPierre Flori  Reviewers:  Peter Bruin 
Report Upstream:  N/A  Work issues:  
Branch:  80db6aa (Commits, GitHub, GitLab)  Commit:  80db6aa42f35fb2d6b72eab19d3842be244ceefa 
Dependencies:  Stopgaps: 
Description (last modified by )
A solution is to use random polynomials just as for odd characteristic.
This also replaces calls to power_mod
by calls to pow
with three arguments which uses implementation optimized code for modular exponentiation.
Change History (22)
comment:1 Changed 8 years ago by
 Branch set to u/jpflori/ticket/16162
 Commit set to 485815436aff2eb226271222b697f8fb7b82ae65
 Keywords finite field polynomial root factor added
comment:2 Changed 8 years ago by
 Commit changed from 485815436aff2eb226271222b697f8fb7b82ae65 to a47c436dda5d87d1a31f5c3a7e2eda33ace7c121
Branch pushed to git repo; I updated commit sha1. New commits:
a47c436  Correction for previous commit fixing CantorZassenhaus.

comment:3 Changed 8 years ago by
 Commit changed from a47c436dda5d87d1a31f5c3a7e2eda33ace7c121 to b3bda421c87e501b6c586aa6eac63d6d665170cb
Branch pushed to git repo; I updated commit sha1. New commits:
b3bda42  Further little improvements for CantorZassenhaus.

comment:4 Changed 8 years ago by
 Cc defeo pbruin added
 Description modified (diff)
 Summary changed from (x**2+x+a).any_root() over GF(2**k) seemingly loops and cannot be interrupted to CantorZassenhaus may enter infinite loop over GF(2**k) and cannot be interrupted
comment:5 Changed 8 years ago by
 Cc sbesnier added
comment:6 Changed 8 years ago by
 Milestone changed from sage6.2 to sage6.3
comment:7 Changed 8 years ago by
 Description modified (diff)
 Status changed from new to needs_review
This looks good enough for me as a first step toward better factorization over finite fields.
comment:8 Changed 8 years ago by
 Status changed from needs_review to needs_work
Could you add some doctests, e.g. an example that used to fail?
comment:9 Changed 8 years ago by
Nice... while adding tests, I found a way to trigger segfaults.
comment:10 Changed 8 years ago by
 Commit changed from b3bda421c87e501b6c586aa6eac63d6d665170cb to 8c4907cdf92fe61c9bce5b4cda43bbf9c1d4f06d
Branch pushed to git repo; I updated commit sha1. New commits:
8c4907c  Add a few tests for CantorZassenhaus fixes.

comment:11 Changed 8 years ago by
 Commit changed from 8c4907cdf92fe61c9bce5b4cda43bbf9c1d4f06d to 9a10e7bd6c945222bbfdc028a30dfb0293b94c6c
Branch pushed to git repo; I updated commit sha1. New commits:
9a10e7b  Fix previous doctests for CantorZassenhaus.

comment:12 Changed 8 years ago by
 Commit changed from 9a10e7bd6c945222bbfdc028a30dfb0293b94c6c to 630bc0b961ba2d123b1a52883d3a20dc240a506d
Branch pushed to git repo; I updated commit sha1. New commits:
630bc0b  Better syntax for CantorZassenhaus doctest.

comment:13 Changed 8 years ago by
 Commit changed from 630bc0b961ba2d123b1a52883d3a20dc240a506d to 27ae9b7af575319e469a9dc5f6dadbd97daeb041
Branch pushed to git repo; I updated commit sha1. New commits:
27ae9b7  Better use of modular exponentiation in CantorZassenhaus + sig_on magic.

comment:14 Changed 8 years ago by
Peter, please have a look at the sig_on/sig_off
stuff.
I'm not sure what I've done is robust or even makes sense.
comment:15 Changed 8 years ago by
You should not put anything inside a sig_on()...sig_off()
block that can interfere with the Python interpreter. From the code it is not clear (to me) if that can happen.
Is the sig_on()...sig_off()
to prevent segfaults, to allow the code to be interrupted, or both? If it is to prevent segfaults, you have to find out where this occurs (this can hopefully be narrowed down to pure Cython code with no calls to the Python interpreter) and wrap this as tightly as possible in sig_on()...sig_off()
. If it is to allow ControlC, alarm()
etc., you can also periodically check for interrupts (I don't remember the details right now).
comment:16 Changed 8 years ago by
Nope, the segfaults were surely caused by the x**q
computation with q = 2**50
(some overflow in NTL I'd say, but the issue might be a real one, at least now it does not happen anymore).
I added the sig_on
magic to ensure you can interrupt the code (even in some of the while
loops, not only because of x**q
with large q
stuff).
But it seems to me that some sig_on
are now useless and potentially wrong as some Python code might get called at some point (in the spirit of your Python interpreter remark I guess), even if it wasn't before, maybe because of the pow
modifications, though it does not really make sense to me.
Maybe some of the sig_on
should be removed, but I'd definitely say some are needed.
Feel free to have a deeper look and modify the code, I won't touch that before tuesday.
comment:17 Changed 8 years ago by
 Commit changed from 27ae9b7af575319e469a9dc5f6dadbd97daeb041 to fa6d50945e36f4145c3d68efdc846a2f224af690
comment:18 Changed 8 years ago by
FYI, the segfault I got was really from:
sage: K.<a> = GF(2**10) sage: R.<x> = K[] sage: x**(2**33)
(Which really needs to ba allowed to be interrupted, and to be faster (for exp < 2**33
), and fixed of course (for exp >= 2**33
)...)
comment:19 Changed 8 years ago by
 Commit changed from fa6d50945e36f4145c3d68efdc846a2f224af690 to 80db6aa42f35fb2d6b72eab19d3842be244ceefa
Branch pushed to git repo; I updated commit sha1. New commits:
80db6aa  Add sig_on magic for NTL polynomial exponentiation.

comment:20 Changed 8 years ago by
 Status changed from needs_work to needs_review
Ok, the latest commit does not seem enough to let NTL be interrupted when allocating a huge array or something like that. Not sure why.
Anyhow, this is not necessary to fix Sage's CZ implem and can be postponed.
comment:21 Changed 8 years ago by
 Reviewers set to Peter Bruin
 Status changed from needs_review to positive_review
comment:22 Changed 8 years ago by
 Branch changed from u/jpflori/ticket/16162 to 80db6aa42f35fb2d6b72eab19d3842be244ceefa
 Resolution set to fixed
 Status changed from positive_review to closed
The
any_root
should surely be refactored as well. That will ease the implementation of special case more efficient methods.New commits:
Quick fix for infinite loop and bugs in CantorZassenhaus implementation.