Opened 5 years ago

Closed 5 years ago

#16983 closed enhancement (fixed)

Fix finite field modulus handling

Reported by: jdemeyer Owned by:
Priority: major Milestone: sage-6.4
Component: finite rings Keywords:
Cc: pbruin, jpflori Merged in:
Authors: Jeroen Demeyer Reviewers: Jean-Pierre Flori
Report Upstream: N/A Work issues:
Branch: 0d9b5cc (Commits) Commit: 0d9b5cc5b2a13e89349b1505c31c2329f6c65ce7
Dependencies: #16934 Stopgaps:

Description (last modified by jdemeyer)

For prime finite fields, we should support a custom modulus (internally in Sage, we don't need to use this modulus in the backend):

sage: x = polygen(GF(7))
sage: k = GF(7, modulus=x+5)
sage: k.modulus()
x + 6
sage: k.gen()
1

We should also make the modulus monic:

sage: x = polygen(GF(7))
sage: k.<a> = GF(7^2, modulus=2*x^2-3, impl="pari_ffelt")
sage: k.modulus()
2*x^2 + 4

(the Givaro backend does this implicitly)

The patch does the above, with lots of cleaning up.

Change History (20)

comment:1 Changed 5 years ago by jdemeyer

  • Description modified (diff)

comment:2 Changed 5 years ago by jdemeyer

  • Dependencies set to #16934

comment:3 Changed 5 years ago by jdemeyer

  • Authors set to Jeroen Demeyer
  • Description modified (diff)

comment:4 Changed 5 years ago by jdemeyer

  • Branch set to u/jdemeyer/ticket/16983
  • Created changed from 09/15/14 08:20:27 to 09/15/14 08:20:27
  • Modified changed from 09/15/14 16:05:35 to 09/15/14 16:05:35

comment:5 Changed 5 years ago by jdemeyer

  • Commit set to eb5553e60dcc353ecefed264a0d0a12b5a490307
  • Status changed from new to needs_review

New commits:

8f805a2Trac 16934: always put finite field implementation in factory key
8923777Trac 16934: remove method FiniteFieldFactory.other_keys()
5e2681eTrac 16934: more cleaning up
ffb74faTrac 16934: add doctest
33c86efMerge remote-tracking branch 'origin/develop' into ticket/16934
bf36ec1Trac 16934: put back (temporary?) warning about modulus parameter
9cbdcdeTrac 16934: fix warning about ignored 'modulus' argument
eb5553eTrac #16983: no longer ignore modulus for prime finite fields

comment:6 Changed 5 years ago by git

  • Commit changed from eb5553e60dcc353ecefed264a0d0a12b5a490307 to b6a6c669c7f8c1a2efd0da70da1f25c1d60663bc

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

b6a6c66Trivial changes to the FiniteField_pari_ffelt constructor

comment:7 Changed 5 years ago by jdemeyer

  • Description modified (diff)

comment:8 Changed 5 years ago by jpflori

  • Cc jpflori added

comment:9 Changed 5 years ago by jpflori

I get a failing doctest in src/sage/rings/finite_rings/homset.py because some ordering changed.

comment:10 Changed 5 years ago by git

  • Commit changed from b6a6c669c7f8c1a2efd0da70da1f25c1d60663bc to f7eccdc0618cdf3f86ef61dcd9e7a4ef9dd09b22

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

f7eccdcMerge remote-tracking branch 'origin/develop' into ticket/16983

comment:11 Changed 5 years ago by jdemeyer

  • Status changed from needs_review to needs_work

comment:12 Changed 5 years ago by git

  • Commit changed from f7eccdc0618cdf3f86ef61dcd9e7a4ef9dd09b22 to dd16a7540f48908e7e38993d6fab4b23301b46c5

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

dd16a75Fix order in doctest output

comment:13 Changed 5 years ago by git

  • Commit changed from dd16a7540f48908e7e38993d6fab4b23301b46c5 to 5028e1099bc7544a9ab7baedbaa4655ddfd4d8c5

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

5028e10Fix infinite loop in unpickling

comment:14 Changed 5 years ago by jdemeyer

  • Status changed from needs_work to needs_review

New commits:

5028e10Fix infinite loop in unpickling

comment:15 follow-up: Changed 5 years ago by jpflori

There is something missing here:

+ def polynomial(self, name=None):
+ """
+ Return the irreducible characteristic polynomial of the
+ generator of this finite field, i.e., the polynomial `f(x)` so
+ elements of the finite field as elements modulo `f`.

comment:16 Changed 5 years ago by jpflori

Otherwise, this looks fine to me and all tests pass. I'll give a final look a little bit later this afternoon.

comment:17 Changed 5 years ago by git

  • Commit changed from 5028e1099bc7544a9ab7baedbaa4655ddfd4d8c5 to 0d9b5cc5b2a13e89349b1505c31c2329f6c65ce7

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

0d9b5ccClarify docs for polynomial()

comment:18 in reply to: ↑ 15 Changed 5 years ago by jdemeyer

Replying to jpflori:

There is something missing here:

+ def polynomial(self, name=None):
+ """
+ Return the irreducible characteristic polynomial of the
+ generator of this finite field, i.e., the polynomial `f(x)` so
+ elements of the finite field as elements modulo `f`.

I just moved that sentence, in fact it dates back to

commit a4928b0cf450b765c3bde6e5328f0146603526a8
Author: tornaria <tornaria@math.utexas.edu>
Date:   Sat Feb 11 01:13:08 2006 +0000

    [project @ original sage-0.10.12]


New commits:

0d9b5ccClarify docs for polynomial()

comment:19 Changed 5 years ago by jpflori

  • Reviewers set to Jean-Pierre Flori
  • Status changed from needs_review to positive_review

Ok, looks good to me.

comment:20 Changed 5 years ago by vbraun

  • Branch changed from u/jdemeyer/ticket/16983 to 0d9b5cc5b2a13e89349b1505c31c2329f6c65ce7
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.