Cantor-Zassenhaus may enter infinite loop over GF(2**k) and cannot be interrupted

[jpflori]

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.

CC: @defeo @pjbruin @sagetrac-sbesnier

Component: finite rings

Keywords: finite field polynomial root factor

Author: Jean-Pierre Flori

Branch/Commit: 80db6aa

Reviewer: Peter Bruin

Issue created by migration from https://trac.sagemath.org/ticket/16162

[jpflori]

Commit: 4858154

[jpflori]

Author: Jean-Pierre Flori

[jpflori]

Changed keywords from none to finite field polynomial root factor

[jpflori]

Branch: u/jpflori/ticket/16162

[jpflori]

comment:1

The any_root should surely be refactored as well.
That will ease the implementation of special case more efficient methods.

---

New commits:

4858154

Quick fix for infinite loop and bugs in Cantor-Zassenhaus implementation.

[sagetrac-git]

Changed commit from 4858154 to a47c436

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

a47c436

Correction for previous commit fixing Cantor-Zassenhaus.

[sagetrac-git]

Changed commit from a47c436 to b3bda42

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

b3bda42

Further little improvements for Cantor-Zassenhaus.

[jpflori]

comment:7

This looks good enough for me as a first step toward better factorization over finite fields.

[pjbruin]

comment:8

Could you add some doctests, e.g. an example that used to fail?

[jpflori]

comment:9

Nice... while adding tests, I found a way to trigger segfaults.

[sagetrac-git]

Changed commit from b3bda42 to 8c4907c

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

8c4907c

Add a few tests for Cantor-Zassenhaus fixes.

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

9a10e7b

Fix previous doctests for Cantor-Zassenhaus.

[sagetrac-git]

Changed commit from 8c4907c to 9a10e7b

[sagetrac-git]

Changed commit from 9a10e7b to 630bc0b

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

630bc0b

Better syntax for Cantor-Zassenhaus doctest.

[sagetrac-git]

Changed commit from 630bc0b to 27ae9b7

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

27ae9b7

Better use of modular exponentiation in Cantor-Zassenhaus + sig_on magic.

[jpflori]

comment:14

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.

[pjbruin]

comment:15

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 Control-C, alarm() etc., you can also periodically check for interrupts (I don't remember the details right now).

[jpflori]

comment:16

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.

[sagetrac-git]

Changed commit from 27ae9b7 to fa6d509

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

d00de84	Add examples for Cantor-Zassenhaus.
fa6d509	Another try for Cantor-Zassenhaus without si_on/off.

[jpflori]

comment:18

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)...)

[sagetrac-git]

Changed commit from fa6d509 to 80db6aa

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

80db6aa

Add sig_on magic for NTL polynomial exponentiation.

[jpflori]

comment:20

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.

[pjbruin]

Reviewer: Peter Bruin

[vbraun]

Changed branch from u/jpflori/ticket/16162 to 80db6aa