Opened 8 years ago

Closed 8 years ago

#16162 closed defect (fixed)

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

Reported by: jpflori Owned by:
Priority: critical Milestone: sage-6.3
Component: finite rings Keywords: finite field polynomial root factor
Cc: defeo, pbruin, sbesnier Merged in:
Authors: Jean-Pierre Flori Reviewers: Peter Bruin
Report Upstream: N/A Work issues:
Branch: 80db6aa (Commits, GitHub, GitLab) Commit: 80db6aa42f35fb2d6b72eab19d3842be244ceefa
Dependencies: Stopgaps:

Status badges

Description (last modified by 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.

Change History (22)

comment:1 Changed 8 years ago by jpflori

  • Authors set to Jean-Pierre Flori
  • Branch set to u/jpflori/ticket/16162
  • Commit set to 485815436aff2eb226271222b697f8fb7b82ae65
  • Keywords finite field polynomial root factor added

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


New commits:

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

comment:2 Changed 8 years ago by git

  • Commit changed from 485815436aff2eb226271222b697f8fb7b82ae65 to a47c436dda5d87d1a31f5c3a7e2eda33ace7c121

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

a47c436Correction for previous commit fixing Cantor-Zassenhaus.

comment:3 Changed 8 years ago by git

  • Commit changed from a47c436dda5d87d1a31f5c3a7e2eda33ace7c121 to b3bda421c87e501b6c586aa6eac63d6d665170cb

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

b3bda42Further little improvements for Cantor-Zassenhaus.

comment:4 Changed 8 years ago by jpflori

  • 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 Cantor-Zassenhaus may enter infinite loop over GF(2**k) and cannot be interrupted

comment:5 Changed 8 years ago by sbesnier

  • Cc sbesnier added

comment:6 Changed 8 years ago by vbraun_spam

  • Milestone changed from sage-6.2 to sage-6.3

comment:7 Changed 8 years ago by jpflori

  • 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 pbruin

  • 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 jpflori

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

comment:10 Changed 8 years ago by git

  • Commit changed from b3bda421c87e501b6c586aa6eac63d6d665170cb to 8c4907cdf92fe61c9bce5b4cda43bbf9c1d4f06d

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

8c4907cAdd a few tests for Cantor-Zassenhaus fixes.

comment:11 Changed 8 years ago by git

  • Commit changed from 8c4907cdf92fe61c9bce5b4cda43bbf9c1d4f06d to 9a10e7bd6c945222bbfdc028a30dfb0293b94c6c

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

9a10e7bFix previous doctests for Cantor-Zassenhaus.

comment:12 Changed 8 years ago by git

  • Commit changed from 9a10e7bd6c945222bbfdc028a30dfb0293b94c6c to 630bc0b961ba2d123b1a52883d3a20dc240a506d

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

630bc0bBetter syntax for Cantor-Zassenhaus doctest.

comment:13 Changed 8 years ago by git

  • Commit changed from 630bc0b961ba2d123b1a52883d3a20dc240a506d to 27ae9b7af575319e469a9dc5f6dadbd97daeb041

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

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

comment:14 Changed 8 years ago by jpflori

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 pbruin

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

comment:16 Changed 8 years ago by jpflori

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.

Last edited 8 years ago by jpflori (previous) (diff)

comment:17 Changed 8 years ago by git

  • Commit changed from 27ae9b7af575319e469a9dc5f6dadbd97daeb041 to fa6d50945e36f4145c3d68efdc846a2f224af690

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

d00de84Add examples for Cantor-Zassenhaus.
fa6d509Another try for Cantor-Zassenhaus without si_on/off.

comment:18 Changed 8 years ago by jpflori

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 git

  • Commit changed from fa6d50945e36f4145c3d68efdc846a2f224af690 to 80db6aa42f35fb2d6b72eab19d3842be244ceefa

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

80db6aaAdd sig_on magic for NTL polynomial exponentiation.

comment:20 Changed 8 years ago by jpflori

  • 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 pbruin

  • Reviewers set to Peter Bruin
  • Status changed from needs_review to positive_review

comment:22 Changed 8 years ago by vbraun

  • Branch changed from u/jpflori/ticket/16162 to 80db6aa42f35fb2d6b72eab19d3842be244ceefa
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.