Opened 9 years ago
Last modified 5 years ago
#13215 closed enhancement
Skew polynomials — at Version 9
Reported by: | caruso | Owned by: | tbd |
---|---|---|---|
Priority: | major | Milestone: | sage-7.4 |
Component: | algebra | Keywords: | skew polynomials, sd75 |
Cc: | tfeulner, caruso, burcin, jsrn, dlucas, tscrim | Merged in: | |
Authors: | Reviewers: | ||
Report Upstream: | N/A | Work issues: | |
Branch: | Commit: | ||
Dependencies: | #13214, #13303 | Stopgaps: |
Description (last modified by )
If R is a ring equipped with an endomorphism sigma, the ring of skew polynomials over (R,sigma) is the ring of usual polynomials over R with the modified multiplication given by the rule X*a = sigma(a)*X.
Skew polynomials play an important role in several domains like coding theory or Galois representations theory in positive characteristic.
The attached patch provides:
- a basic implementation of skew polynomials over any commutative ring (including addition, multiplication, euclidean division, gcd...)
- a more complete implementation of skew polynomials over finite fields (including factoring)
NB: This ticket depends on tickets #13214 (which implements Frobenius endomorphisms over finite fields) and #13303 (which fixes a bug in quotient_polynomial_ring_element.pyx). For convenience, I reattach the corresponding patches here (you need to apply these two patches first).
Change History (11)
comment:1 Changed 9 years ago by
- Status changed from new to needs_review
comment:2 Changed 9 years ago by
- Dependencies set to #13214
- Description modified (diff)
Changed 9 years ago by
comment:3 Changed 9 years ago by
comment:4 Changed 9 years ago by
- Cc tfeulner added
- Status changed from needs_review to needs_work
With your changes it is now possible to test some element in an Univariate Quotient Polynomial Ring to be a unit and to compute its inverse. Unfortunately, this computation gives wrong results:
sage: Z16x.<x> = Integers(16)[] sage: GR.<y> = Z16x.quotient(x**2 + x+1 ) sage: (2*y).is_unit() True sage: (2*y)^(-1) 15*y + 15 sage: (2*y)*(2*y)^(-1) 2
Thomas
comment:5 Changed 9 years ago by
Thanks for catching this!
I've updated my patch. (I've simply decided to raise a NotImplementedError? when the base ring is not a field and, by the way, I've added some doctests.)
PS: apply patch trac_13215_skew_polynomials.patch and forget trac_13215_skew_polynomials.2.patch (is it possible to remove it?)
comment:6 Changed 9 years ago by
- Status changed from needs_work to needs_review
comment:7 Changed 9 years ago by
Maybe you should produce a seperate trac ticket for the fix of
sage: (2*y)^(-1) ... NotImplementedError: The base ring (=Ring of integers modulo 16) is not a field
By the way, I know that this is a problem which also occurs for usual polynomials (because of the default definition of the reduce function). Do you have any idea how to fix this:
sage: Z16x.<x> = SkewPolynomialRing(Integers(16)) sage: # Z16x.<x> = Integers(16)[] # has the same behaviour sage: GR.<y> = Z16x.quotient(x**2 + x+1 ) sage: I = GR.ideal(4) sage: I.reduce(6) 6
Changed 9 years ago by
comment:8 Changed 9 years ago by
Ok, I split my patch in two parts and I open a new ticket (cf #13303).
I'm afraid I don't understand quite well the problem with reduce. Could you explain it a bit more please?
comment:9 Changed 9 years ago by
- Dependencies changed from #13214 to #13214, #13303
- Description modified (diff)
File trac_13215_skew_polynomials.2.patch replaces trac_13215_skew_polynomials.patch