Hot-keys on this page
r m x p toggle line displays
j k next/prev highlighted chunk
0 (zero) top of page
1 (one) first highlighted chunk
"Univariate rational functions over prime fields" from __future__ import print_function, absolute_import
from cysignals.signals cimport sig_on, sig_off
from sage.libs.gmp.mpz cimport * from sage.libs.flint.nmod_poly cimport * from sage.libs.flint.ulong_extras cimport n_jacobi from sage.structure.element cimport Element, ModuleElement, RingElement from sage.rings.finite_rings.integer_mod cimport IntegerMod_int from sage.rings.integer cimport Integer from sage.rings.polynomial.polynomial_zmod_flint cimport Polynomial_zmod_flint, get_cparent
from sage.rings.finite_rings.integer_mod cimport mod_inverse_int
""" This class represents the fraction field GF(p)(T) for `2 < p < 2^16`.
EXAMPLES::
sage: R.<T> = GF(71)[] sage: K = FractionField(R); K Fraction Field of Univariate Polynomial Ring in T over Finite Field of size 71 sage: 1-1/T (T + 70)/T sage: parent(1-1/T) is K True """ """ INPUT:
- ``R`` -- A polynomial ring over a finite field of prime order `p` with `2 < p < 2^16`
EXAMPLES::
sage: R.<x> = GF(31)[] sage: K = R.fraction_field(); K Fraction Field of Univariate Polynomial Ring in x over Finite Field of size 31 """
""" Returns an iterator over this fraction field.
EXAMPLES::
sage: R.<t> = GF(3)[]; K = R.fraction_field() sage: iter(K) <sage.rings.fraction_field_FpT.FpT_iter object at ...> """
""" EXAMPLES::
sage: from sage.rings.fraction_field_FpT import * sage: R.<t> = FpT(GF(5)['t']) sage: list(R.iter(2))[350:355] [(t^2 + t + 1)/(t + 2), (t^2 + t + 2)/(t + 2), (t^2 + t + 4)/(t + 2), (t^2 + 2*t + 1)/(t + 2), (t^2 + 2*t + 2)/(t + 2)] """
cdef class FpTElement(RingElement): """ An element of an FpT fraction field. """
def __init__(self, parent, numer, denom=1, coerce=True, reduce=True): """ INPUT:
- parent -- the Fraction field containing this element - numer -- something that can be converted into the polynomial ring, giving the numerator - denom -- something that can be converted into the polynomial ring, giving the numerator (default 1)
EXAMPLES::
sage: from sage.rings.fraction_field_FpT import * sage: R.<t> = FpT(GF(5)['t']) sage: R(7) 2 """ cdef long n
def __dealloc__(self): """ Deallocation.
EXAMPLES::
sage: K = GF(11)['t'].fraction_field() sage: t = K.gen() sage: del t # indirect doctest """
def __reduce__(self): """ For pickling.
TESTS::
sage: K = GF(11)['t'].fraction_field() sage: loads(dumps(K.gen())) t sage: loads(dumps(1/K.gen())) 1/t """
cdef FpTElement _new_c(self): """ Creates a new FpTElement in the same field, leaving the value to be initialized. """
cdef FpTElement _copy_c(self): """ Creates a new FpTElement in the same field, with the same value as self. """
def numer(self): """ Returns the numerator of this element, as an element of the polynomial ring.
EXAMPLES::
sage: K = GF(11)['t'].fraction_field() sage: t = K.gen(0); a = (t + 1/t)^3 - 1 sage: a.numer() t^6 + 3*t^4 + 10*t^3 + 3*t^2 + 1 """
cpdef numerator(self): """ Returns the numerator of this element, as an element of the polynomial ring.
EXAMPLES::
sage: K = GF(11)['t'].fraction_field() sage: t = K.gen(0); a = (t + 1/t)^3 - 1 sage: a.numerator() t^6 + 3*t^4 + 10*t^3 + 3*t^2 + 1 """
def denom(self): """ Returns the denominator of this element, as an element of the polynomial ring.
EXAMPLES::
sage: K = GF(11)['t'].fraction_field() sage: t = K.gen(0); a = (t + 1/t)^3 - 1 sage: a.denom() t^3 """
cpdef denominator(self): """ Returns the denominator of this element, as an element of the polynomial ring.
EXAMPLES::
sage: K = GF(11)['t'].fraction_field() sage: t = K.gen(0); a = (t + 1/t)^3 - 1 sage: a.denominator() t^3 """
def __call__(self, *args, **kwds): """ EXAMPLES::
sage: K = Frac(GF(5)['t']) sage: t = K.gen() sage: t(3) 3 sage: f = t^2/(1-t) sage: f(2) 1 sage: f(t) 4*t^2/(t + 4) sage: f(t^3) 4*t^6/(t^3 + 4) sage: f((t+1)/t^3) (t^2 + 2*t + 1)/(t^6 + 4*t^4 + 4*t^3) """
def subs(self, *args, **kwds): """ EXAMPLES::
sage: K = Frac(GF(11)['t']) sage: t = K.gen() sage: f = (t+1)/(t-1) sage: f.subs(t=2) 3 sage: f.subs(X=2) (t + 1)/(t + 10) """
def valuation(self, v): """ Returns the valuation of self at `v`.
EXAMPLES::
sage: R.<t> = GF(5)[] sage: f = (t+1)^2 * (t^2+t+1) / (t-1)^3 sage: f.valuation(t+1) 2 sage: f.valuation(t-1) -3 sage: f.valuation(t) 0 """
def factor(self): """ EXAMPLES::
sage: K = Frac(GF(5)['t']) sage: t = K.gen() sage: f = 2 * (t+1) * (t^2+t+1)^2 / (t-1) sage: factor(f) (2) * (t + 4)^-1 * (t + 1) * (t^2 + t + 1)^2 """
def _repr_(self): """ Returns a string representation of this element.
EXAMPLES::
sage: from sage.rings.fraction_field_FpT import * sage: R.<t> = FpT(GF(17)['t']) sage: -t # indirect doctest 16*t sage: 1/t 1/t sage: 1/(t+1) 1/(t + 1) sage: 1-t/t 0 sage: (1-t)/t (16*t + 1)/t """ else:
def _latex_(self): r""" Returns a latex representation of this element.
EXAMPLES::
sage: K = GF(7)['t'].fraction_field(); t = K.gen(0) sage: latex(t^2 + 1) # indirect doctest t^{2} + 1 sage: latex((t + 1)/(t-1)) \frac{t + 1}{t + 6} """ else:
cpdef int _cmp_(self, other) except -2: """ Compares this with another element. The ordering is arbitrary, but it is an ordering, and it is consistent between runs. It has nothing to do with the algebra structure.
TESTS::
sage: from sage.rings.fraction_field_FpT import * sage: R.<t> = FpT(GF(7)['t']) sage: t == t True sage: t == -t False sage: -t == 6*t True sage: 1/t == 1/t True sage: 1/t == 1/(t+1) False sage: 2*t/t == 2 True sage: 2*t/2 == t True
sage: a = (t^3 + 3*t)/(5*t-2); b = (t^2-2)/(t-1) sage: b < a True sage: a < b False sage: 1/a < b True sage: b < 1/a False
::
sage: K = Frac(GF(5)['t']); t = K.gen() sage: t == 1 False sage: t + 1 < t^2 True """ # They are normalized.
def __hash__(self): """ Returns a hash value for this element.
TESTS::
sage: from sage.rings.fraction_field_FpT import * sage: K.<t> = FpT(GF(7)['t']) sage: hash(K(0)) 0 sage: hash(K(5)) 5 sage: set([1, t, 1/t, t, t, 1/t, 1+1/t, t/t]) {1, 1/t, t, (t + 1)/t} sage: a = (t+1)/(t^2-1); hash(a) == hash((a.numer(),a.denom())) True """
def __neg__(self): """ Negates this element.
EXAMPLES::
sage: K = GF(5)['t'].fraction_field(); t = K.gen(0) sage: a = (t^2 + 2)/(t-1) sage: -a # indirect doctest (4*t^2 + 3)/(t + 4) """
def __invert__(self): """ Returns the multiplicative inverse of this element.
EXAMPLES::
sage: K = GF(5)['t'].fraction_field(); t = K.gen(0) sage: a = (t^2 + 2)/(t-1) sage: ~a # indirect doctest (t + 4)/(t^2 + 2) """ raise ZeroDivisionError
cpdef _add_(self, _other): """ Returns the sum of this fraction field element and another.
EXAMPLES::
sage: from sage.rings.fraction_field_FpT import * sage: R.<t> = FpT(GF(7)['t']) sage: t + t # indirect doctest 2*t sage: (t + 3) + (t + 10) 2*t + 6 sage: sum([t] * 7) 0 sage: 1/t + t (t^2 + 1)/t sage: 1/t + 1/t^2 (t + 1)/t^2 """
cpdef _sub_(self, _other): """ Returns the difference of this fraction field element and another.
EXAMPLES::
sage: from sage.rings.fraction_field_FpT import * sage: R.<t> = FpT(GF(7)['t']) sage: t - t # indirect doctest 0 sage: (t + 3) - (t + 11) 6 """
cpdef _mul_(self, _other): """ Returns the product of this fraction field element and another.
EXAMPLES::
sage: from sage.rings.fraction_field_FpT import * sage: R.<t> = FpT(GF(7)['t']) sage: t * t # indirect doctest t^2 sage: (t + 3) * (t + 10) t^2 + 6*t + 2 """
cpdef _div_(self, _other): """ Returns the quotient of this fraction field element and another.
EXAMPLES::
sage: from sage.rings.fraction_field_FpT import * sage: R.<t> = FpT(GF(5)['t']) sage: t / t # indirect doctest 1 sage: (t + 3) / (t + 11) (t + 3)/(t + 1) sage: (t^2 + 2*t + 1) / (t + 1) t + 1 """ raise ZeroDivisionError
cpdef FpTElement next(self): """ This function iterates through all polynomials, returning the "next" polynomial after this one.
The strategy is as follows:
- We always leave the denominator monic.
- We progress through the elements with both numerator and denominator monic, and with the denominator less than the numerator. For each such, we output all the scalar multiples of it, then all of the scalar multiples of its inverse.
- So if the leading coefficient of the numerator is less than p-1, we scale the numerator to increase it by 1.
- Otherwise, we consider the multiple with numerator and denominator monic.
- If the numerator is less than the denominator (lexicographically), we return the inverse of that element.
- If the numerator is greater than the denominator, we invert, and then increase the numerator (remaining monic) until we either get something relatively prime to the new denominator, or we reach the new denominator. In this case, we increase the denominator and set the numerator to 1.
EXAMPLES::
sage: from sage.rings.fraction_field_FpT import * sage: R.<t> = FpT(GF(3)['t']) sage: a = R(0) sage: for _ in range(30): ....: a = a.next() ....: print(a) 1 2 1/t 2/t t 2*t 1/(t + 1) 2/(t + 1) t + 1 2*t + 2 t/(t + 1) 2*t/(t + 1) (t + 1)/t (2*t + 2)/t 1/(t + 2) 2/(t + 2) t + 2 2*t + 1 t/(t + 2) 2*t/(t + 2) (t + 2)/t (2*t + 1)/t (t + 1)/(t + 2) (2*t + 2)/(t + 2) (t + 2)/(t + 1) (2*t + 1)/(t + 1) 1/t^2 2/t^2 t^2 2*t^2 """ cdef long a, lead cdef nmod_poly_t g # self should be normalized, so denom == 1 # no overflow since self.p < 2^16 else: # now both next._numer and next._denom are monic. We figure out which is lexicographically bigger: # next._numer and next._denom are relatively prime, so they're both 1. # since next._numer is smaller, we flip and return the inverse. # since next._numer is bigger, we're in the flipped phase. We flip back, and increment the numerator (until we reach the denominator). # Since we've reached the denominator, we reset the numerator to 1 and increment the denominator. else: # otherwise, we keep incrementing until we have a relatively prime numerator. finally:
cpdef _sqrt_or_None(self): """ Return the square root of ``self``, or ``None``.
Differs from sqrt() by not raising an exception.
TESTS::
sage: from sage.rings.fraction_field_FpT import * sage: R.<t> = FpT(GF(17)['t']) sage: sqrt(t^2) # indirect doctest t sage: sqrt(1/t^2) 1/t sage: sqrt((1+t)^2) t + 1 sage: sqrt((1+t)^2 / t^2) (t + 1)/t
sage: sqrt(4 * (1+t)^2 / t^2) (2*t + 2)/t
sage: sqrt(R(0)) 0 sage: sqrt(R(-1)) 4
sage: sqrt(t^4) t^2 sage: sqrt(4*t^4/(1+t)^8) 2*t^2/(t^4 + 4*t^3 + 6*t^2 + 4*t + 1)
sage: R.<t> = FpT(GF(5)['t']) sage: [a for a in R.iter(2) if (a^2).sqrt() not in (a,-a)] [] sage: [a for a in R.iter(2) if a.is_square() and a.sqrt()^2 != a] [] """
cdef nmod_poly_t numer cdef nmod_poly_t denom cdef long a cdef FpTElement res
# Make denominator monic # Choose numerator with smaller leading coefficient else:
cpdef bint is_square(self): """ Returns True if this element is the square of another element of the fraction field.
EXAMPLES::
sage: K = GF(13)['t'].fraction_field(); t = K.gen() sage: t.is_square() False sage: (1/t^2).is_square() True sage: K(0).is_square() True """
def sqrt(self, extend=True, all=False): """ Returns the square root of this element.
INPUT:
- ``extend`` - bool (default: True); if True, return a square root in an extension ring, if necessary. Otherwise, raise a ValueError if the square is not in the base ring.
- ``all`` - bool (default: False); if True, return all square roots of self, instead of just one.
EXAMPLES::
sage: from sage.rings.fraction_field_FpT import * sage: K = GF(7)['t'].fraction_field(); t = K.gen(0) sage: p = (t + 2)^2/(3*t^3 + 1)^4 sage: p.sqrt() (3*t + 6)/(t^6 + 3*t^3 + 4) sage: p.sqrt()^2 == p True """ if extend: raise NotImplementedError("function fields not yet implemented") else: raise ValueError("not a perfect square") else: if not s: return [s] else: return [s, -s] else:
def __pow__(FpTElement self, Py_ssize_t e, dummy): """ Returns the ``e``th power of this element.
EXAMPLES::
sage: from sage.rings.fraction_field_FpT import * sage: R.<t> = FpT(GF(7)['t']) sage: t^5 t^5 sage: t^-5 1/t^5
sage: a = (t+1)/(t-1); a (t + 1)/(t + 6) sage: a^5 (t^5 + 5*t^4 + 3*t^3 + 3*t^2 + 5*t + 1)/(t^5 + 2*t^4 + 3*t^3 + 4*t^2 + 5*t + 6) sage: a^7 (t^7 + 1)/(t^7 + 6) sage: a^14 (t^14 + 2*t^7 + 1)/(t^14 + 5*t^7 + 1)
sage: (a^2)^2 == a^4 True sage: a^3 * a^2 == a^5 True sage: a^47 * a^92 == a^(47+92) True """ cdef long a else: a = mod_inverse_int(nmod_poly_leading(x._denom), self.p) nmod_poly_scalar_mul_nmod(x._numer, x._numer, a) nmod_poly_scalar_mul_nmod(x._denom, x._denom, a)
cdef class FpT_iter: """ Returns a class that iterates over all elements of an FpT.
EXAMPLES::
sage: K = GF(3)['t'].fraction_field() sage: I = K.iter(1) sage: list(I) [0, 1, 2, t, t + 1, t + 2, 2*t, 2*t + 1, 2*t + 2, 1/t, 2/t, (t + 1)/t, (t + 2)/t, (2*t + 1)/t, (2*t + 2)/t, 1/(t + 1), 2/(t + 1), t/(t + 1), (t + 2)/(t + 1), 2*t/(t + 1), (2*t + 1)/(t + 1), 1/(t + 2), 2/(t + 2), t/(t + 2), (t + 1)/(t + 2), 2*t/(t + 2), (2*t + 2)/(t + 2)] """ def __init__(self, parent, degree=None, FpTElement start=None): """ INPUT:
- parent -- The FpT that we're iterating over.
- degree -- The maximum degree of the numerator and denominator of the elements over which we iterate.
- start -- (default 0) The element on which to start.
EXAMPLES::
sage: K = GF(11)['t'].fraction_field() sage: I = K.iter(2) # indirect doctest sage: for a in I: ....: if a.denom()[0] == 3 and a.numer()[1] == 2: ....: print(a); break 2*t/(t + 3) """ #if degree is None: # raise NotImplementedError
def __cinit__(self, parent, *args, **kwds): """ Memory allocation for the temp variable storing the gcd of the numerator and denominator.
TESTS::
sage: from sage.rings.fraction_field_FpT import FpT_iter sage: K = GF(7)['t'].fraction_field() sage: I = FpT_iter(K, 3) # indirect doctest sage: I <sage.rings.fraction_field_FpT.FpT_iter object at ...> """
def __dealloc__(self): """ Deallocating of self.g.
TESTS::
sage: from sage.rings.fraction_field_FpT import FpT_iter sage: K = GF(7)['t'].fraction_field() sage: I = FpT_iter(K, 3) sage: del I # indirect doctest """
def __iter__(self): """ Returns this iterator.
TESTS::
sage: from sage.rings.fraction_field_FpT import FpT_iter sage: K = GF(3)['t'].fraction_field() sage: I = FpT_iter(K, 3) sage: for a in I: # indirect doctest ....: if a.numer()[1] == 1 and a.denom()[1] == 2 and a.is_square(): ....: print(a); break (t^2 + t + 1)/(t^2 + 2*t + 1) """
def __next__(self): """ Returns the next element to iterate over.
This is achieved by iterating over monic denominators, and for each denominator, iterating over all numerators relatively prime to the given denominator.
EXAMPLES::
sage: from sage.rings.fraction_field_FpT import * sage: K.<t> = FpT(GF(3)['t']) sage: list(K.iter(1)) # indirect doctest [0, 1, 2, t, t + 1, t + 2, 2*t, 2*t + 1, 2*t + 2, 1/t, 2/t, (t + 1)/t, (t + 2)/t, (2*t + 1)/t, (2*t + 2)/t, 1/(t + 1), 2/(t + 1), t/(t + 1), (t + 2)/(t + 1), 2*t/(t + 1), (2*t + 1)/(t + 1), 1/(t + 2), 2/(t + 2), t/(t + 2), (t + 1)/(t + 2), 2*t/(t + 2), (2*t + 2)/(t + 2)]
sage: len(list(K.iter(3))) 2187
sage: K.<t> = FpT(GF(5)['t']) sage: L = list(K.iter(3)); len(L) 78125 sage: L[:10] [0, 1, 2, 3, 4, t, t + 1, t + 2, t + 3, t + 4] sage: L[2000] (3*t^3 + 3*t^2 + 3*t + 4)/(t + 2) sage: L[-1] (4*t^3 + 4*t^2 + 4*t + 4)/(t^3 + 4*t^2 + 4*t + 4) """ cdef FpTElement next_ self.cur = next(self.cur) else:
cdef class Polyring_FpT_coerce(RingHomomorphism): """ This class represents the coercion map from GF(p)[t] to GF(p)(t)
EXAMPLES::
sage: R.<t> = GF(5)[] sage: K = R.fraction_field() sage: f = K.coerce_map_from(R); f Ring morphism: From: Univariate Polynomial Ring in t over Finite Field of size 5 To: Fraction Field of Univariate Polynomial Ring in t over Finite Field of size 5 sage: type(f) <type 'sage.rings.fraction_field_FpT.Polyring_FpT_coerce'>
TESTS::
TestSuite(f).run()
""" cdef long p
def __init__(self, R): """ INPUT:
- R -- An FpT
EXAMPLES::
sage: R.<t> = GF(next_prime(2000))[] sage: K = R.fraction_field() # indirect doctest """
cdef dict _extra_slots(self): """ Helper for copying and pickling.
EXAMPLES::
sage: R.<t> = GF(5)[] sage: K = R.fraction_field() sage: f = K.coerce_map_from(R) # indirect doctest sage: f(t^2 + 1) t^2 + 1 """
cdef _update_slots(self, dict _slots): """ Helper for copying and pickling.
EXAMPLES::
sage: R.<t> = GF(5)[] sage: K = R.fraction_field() sage: f = K.coerce_map_from(R) # indirect doctest sage: f(t^2 + 1) t^2 + 1 """
cpdef Element _call_(self, _x): """ Applies the coercion.
EXAMPLES::
sage: R.<t> = GF(5)[] sage: K = R.fraction_field() sage: f = K.coerce_map_from(R) sage: f(t^2 + 1) # indirect doctest t^2 + 1 """
""" This function allows the map to take multiple arguments, usually used to specify both numerator and denominator.
If ``reduce`` is specified as False, then the result won't be normalized.
EXAMPLES::
sage: R.<t> = GF(5)[] sage: K = R.fraction_field() sage: f = K.coerce_map_from(R) sage: f(2*t + 2, t + 3) # indirect doctest (2*t + 2)/(t + 3) sage: f(2*t + 2, 2) t + 1 sage: f(2*t + 2, 2, reduce=False) (2*t + 2)/2
TESTS:
Check that :trac:`12217` and :trac:`16811` are fixed::
sage: R.<t> = GF(5)[] sage: K = R.fraction_field() sage: f = K.coerce_map_from(R) sage: f(t, 0) Traceback (most recent call last): ... ZeroDivisionError: fraction has denominator 0 sage: f(t, GF(5).zero()) Traceback (most recent call last): ... ZeroDivisionError: fraction has denominator 0 sage: f(t, R.zero()) Traceback (most recent call last): ... ZeroDivisionError: fraction has denominator 0 """ cdef Polynomial_zmod_flint x cdef unsigned long r nmod_poly_set_coeff_ui(ans._denom, 0, 1) # No need to normalize else: # could use the coerce keyword being set to False to not check this... # We could special case integers and GF(p) elements here. # Normalize the fraction, checking for division by zero else: raise TypeError("FpT only supports two positional arguments")
def section(self): """ Returns the section of this inclusion: the partially defined map from ``GF(p)(t)`` back to ``GF(p)[t]``, defined on elements with unit denominator.
EXAMPLES::
sage: R.<t> = GF(5)[] sage: K = R.fraction_field() sage: f = K.coerce_map_from(R) sage: g = f.section(); g Section map: From: Fraction Field of Univariate Polynomial Ring in t over Finite Field of size 5 To: Univariate Polynomial Ring in t over Finite Field of size 5 sage: t = K.gen() sage: g(t) t sage: g(1/t) Traceback (most recent call last): ... ValueError: not integral """
cdef class FpT_Polyring_section(Section): """ This class represents the section from GF(p)(t) back to GF(p)[t]
EXAMPLES::
sage: R.<t> = GF(5)[] sage: K = R.fraction_field() sage: f = R.convert_map_from(K); f Section map: From: Fraction Field of Univariate Polynomial Ring in t over Finite Field of size 5 To: Univariate Polynomial Ring in t over Finite Field of size 5 sage: type(f) <type 'sage.rings.fraction_field_FpT.FpT_Polyring_section'>
.. WARNING::
Comparison of ``FpT_Polyring_section`` objects is not currently implemented. See :trac: `23469`. ::
sage: fprime = loads(dumps(f)) sage: fprime == f False
sage: fprime(1+t) == f(1+t) True
TESTS::
sage: TestSuite(f).run(skip='_test_pickling')
""" cdef long p
def __init__(self, Polyring_FpT_coerce f): """ INPUT:
- f -- A Polyring_FpT_coerce homomorphism
EXAMPLES::
sage: R.<t> = GF(next_prime(2000))[] sage: K = R.fraction_field() sage: R(K.gen(0)) # indirect doctest t """
cdef dict _extra_slots(self): """ Helper for copying and pickling.
EXAMPLES::
sage: R.<t> = GF(7)[] sage: K = R.fraction_field() sage: f = K.coerce_map_from(R) sage: g = f.section() # indirect doctest sage: t = K.gen() sage: g(t^2) t^2 sage: g(1/t) Traceback (most recent call last): ... ValueError: not integral """
cdef _update_slots(self, dict _slots): """ Helper for copying and pickling.
EXAMPLES::
sage: R.<t> = GF(7)[] sage: K = R.fraction_field() sage: f = K.coerce_map_from(R) sage: g = f.section() # indirect doctest sage: t = K.gen() sage: g(t^2) t^2 sage: g(1/t) Traceback (most recent call last): ... ValueError: not integral """
cpdef Element _call_(self, _x): """ Applies the section.
EXAMPLES::
sage: R.<t> = GF(7)[] sage: K = R.fraction_field() sage: f = K.coerce_map_from(R) sage: g = f.section(); g Section map: From: Fraction Field of Univariate Polynomial Ring in t over Finite Field of size 7 To: Univariate Polynomial Ring in t over Finite Field of size 7 sage: t = K.gen() sage: g(t^2) # indirect doctest t^2 sage: g(1/t) Traceback (most recent call last): ... ValueError: not integral """ cdef Polynomial_zmod_flint ans normalize(x._numer, x._denom, self.p)
cdef class Fp_FpT_coerce(RingHomomorphism): """ This class represents the coercion map from GF(p) to GF(p)(t)
EXAMPLES::
sage: R.<t> = GF(5)[] sage: K = R.fraction_field() sage: f = K.coerce_map_from(GF(5)); f Ring morphism: From: Finite Field of size 5 To: Fraction Field of Univariate Polynomial Ring in t over Finite Field of size 5 sage: type(f) <type 'sage.rings.fraction_field_FpT.Fp_FpT_coerce'>
TESTS::
sage: TestSuite(f).run()
""" cdef long p
def __init__(self, R): """ INPUT:
- R -- An FpT
EXAMPLES::
sage: R.<t> = GF(next_prime(3000))[] sage: K = R.fraction_field() # indirect doctest """
cdef dict _extra_slots(self): """ Helper for copying and pickling.
EXAMPLES::
sage: R.<t> = GF(5)[] sage: K = R.fraction_field() sage: f = K.coerce_map_from(GF(5)) sage: g = copy(f) sage: g == f True sage: g(GF(5)(2)) == f(GF(5)(2)) True """
cdef _update_slots(self, dict _slots): """ Helper for copying and pickling.
EXAMPLES::
sage: R.<t> = GF(5)[] sage: K = R.fraction_field() sage: f = K.coerce_map_from(GF(5)) sage: g = copy(f) sage: g == f True sage: g(GF(5)(2)) == f(GF(5)(2)) True """
cpdef Element _call_(self, _x): """ Applies the coercion.
EXAMPLES::
sage: R.<t> = GF(5)[] sage: K = R.fraction_field() sage: f = K.coerce_map_from(GF(5)) sage: f(GF(5)(3)) # indirect doctest 3 """
""" This function allows the map to take multiple arguments, usually used to specify both numerator and denominator.
If ``reduce`` is specified as False, then the result won't be normalized.
EXAMPLES::
sage: R.<t> = GF(5)[] sage: K = R.fraction_field() sage: f = K.coerce_map_from(GF(5)) sage: f(1, t + 3) # indirect doctest 1/(t + 3) sage: f(2, 2*t) 1/t sage: f(2, 2*t, reduce=False) 2/2*t """ cdef long r nmod_poly_set_coeff_ui(ans._denom, 0, 1) raise ZeroDivisionError else: # could use the coerce keyword being set to False to not check this... # We could special case integers and GF(p) elements here. y = R(y) else: raise ValueError("FpT only supports two positional arguments")
def section(self): """ Returns the section of this inclusion: the partially defined map from ``GF(p)(t)`` back to ``GF(p)``, defined on constant elements.
EXAMPLES::
sage: R.<t> = GF(5)[] sage: K = R.fraction_field() sage: f = K.coerce_map_from(GF(5)) sage: g = f.section(); g Section map: From: Fraction Field of Univariate Polynomial Ring in t over Finite Field of size 5 To: Finite Field of size 5 sage: t = K.gen() sage: g(f(1,3,reduce=False)) 2 sage: g(t) Traceback (most recent call last): ... ValueError: not constant sage: g(1/t) Traceback (most recent call last): ... ValueError: not integral """
cdef class FpT_Fp_section(Section): """ This class represents the section from GF(p)(t) back to GF(p)[t]
EXAMPLES::
sage: R.<t> = GF(5)[] sage: K = R.fraction_field() sage: f = GF(5).convert_map_from(K); f Section map: From: Fraction Field of Univariate Polynomial Ring in t over Finite Field of size 5 To: Finite Field of size 5 sage: type(f) <type 'sage.rings.fraction_field_FpT.FpT_Fp_section'>
.. WARNING::
Comparison of ``FpT_Fp_section`` objects is not currently implemented. See :trac: `23469`. ::
sage: fprime = loads(dumps(f)) sage: fprime == f False
sage: fprime(3) == f(3) True
TESTS::
sage: TestSuite(f).run(skip='_test_pickling')
""" cdef long p
def __init__(self, Fp_FpT_coerce f): """ INPUT:
- f -- An Fp_FpT_coerce homomorphism
EXAMPLES::
sage: R.<t> = GF(next_prime(2000))[] sage: K = R.fraction_field() sage: GF(next_prime(2000))(K(127)) # indirect doctest 127 """
cdef dict _extra_slots(self): """ Helper for copying and pickling.
EXAMPLES::
sage: R.<t> = GF(7)[] sage: K = R.fraction_field() sage: f = K.coerce_map_from(GF(7)) sage: g = f.section() # indirect doctest sage: t = K.gen() sage: g(t^2) Traceback (most recent call last): ... ValueError: not constant sage: g(1/t) Traceback (most recent call last): ... ValueError: not integral sage: g(K(4)) 4 sage: g(K(0)) 0 """
cdef _update_slots(self, dict _slots): """ Helper for copying and pickling.
EXAMPLES::
sage: R.<t> = GF(7)[] sage: K = R.fraction_field() sage: f = K.coerce_map_from(GF(7)) sage: g = f.section() # indirect doctest sage: t = K.gen() sage: g(t^2) Traceback (most recent call last): ... ValueError: not constant sage: g(1/t) Traceback (most recent call last): ... ValueError: not integral sage: g(K(4)) 4 sage: g(K(0)) 0 """
cpdef Element _call_(self, _x): """ Applies the section.
EXAMPLES::
sage: R.<t> = GF(7)[] sage: K = R.fraction_field() sage: f = K.coerce_map_from(GF(7)) sage: g = f.section(); g Section map: From: Fraction Field of Univariate Polynomial Ring in t over Finite Field of size 7 To: Finite Field of size 7 sage: t = K.gen() sage: g(t^2) # indirect doctest Traceback (most recent call last): ... ValueError: not constant sage: g(1/t) Traceback (most recent call last): ... ValueError: not integral sage: g(K(4)) 4 sage: g(K(0)) 0 """ cdef IntegerMod_int ans
cdef class ZZ_FpT_coerce(RingHomomorphism): """ This class represents the coercion map from ZZ to GF(p)(t)
EXAMPLES::
sage: R.<t> = GF(17)[] sage: K = R.fraction_field() sage: f = K.coerce_map_from(ZZ); f Ring morphism: From: Integer Ring To: Fraction Field of Univariate Polynomial Ring in t over Finite Field of size 17 sage: type(f) <type 'sage.rings.fraction_field_FpT.ZZ_FpT_coerce'>
TESTS::
sage: TestSuite(f).run()
""" cdef long p
def __init__(self, R): """ INPUT:
- R -- An FpT
EXAMPLES::
sage: R.<t> = GF(next_prime(3000))[] sage: K = R.fraction_field() # indirect doctest """
cdef dict _extra_slots(self): """ Helper for copying and pickling.
EXAMPLES::
sage: R.<t> = GF(5)[] sage: K = R.fraction_field() sage: f = K.coerce_map_from(ZZ) sage: g = copy(f) # indirect doctest sage: g == f True sage: g(5) == f(5) True sage: g(0) == f(0) True """
cdef _update_slots(self, dict _slots): """ Helper for copying and pickling.
EXAMPLES::
sage: R.<t> = GF(5)[] sage: K = R.fraction_field() sage: f = K.coerce_map_from(ZZ) sage: g = copy(f) # indirect doctest sage: g == f True sage: g(5) == f(5) True sage: g(0) == f(0) True """
cpdef Element _call_(self, _x): """ Applies the coercion.
EXAMPLES::
sage: R.<t> = GF(5)[] sage: K = R.fraction_field() sage: f = K.coerce_map_from(ZZ) sage: f(3) # indirect doctest 3 """
""" This function allows the map to take multiple arguments, usually used to specify both numerator and denominator.
If ``reduce`` is specified as False, then the result won't be normalized.
EXAMPLES::
sage: R.<t> = GF(5)[] sage: K = R.fraction_field() sage: f = K.coerce_map_from(ZZ) sage: f(1, t + 3) # indirect doctest 1/(t + 3) sage: f(1,2) 3 sage: f(2, 2*t) 1/t sage: f(2, 2*t, reduce=False) 2/2*t """ cdef long r nmod_poly_set_coeff_ui(ans._denom, 0, 1) raise ZeroDivisionError else: # could use the coerce keyword being set to False to not check this... # We could special case integers and GF(p) elements here. y = R(y) else: raise ValueError("FpT only supports two positional arguments")
def section(self): """ Returns the section of this inclusion: the partially defined map from ``GF(p)(t)`` back to ``ZZ``, defined on constant elements.
EXAMPLES::
sage: R.<t> = GF(5)[] sage: K = R.fraction_field() sage: f = K.coerce_map_from(ZZ) sage: g = f.section(); g Composite map: From: Fraction Field of Univariate Polynomial Ring in t over Finite Field of size 5 To: Integer Ring Defn: Section map: From: Fraction Field of Univariate Polynomial Ring in t over Finite Field of size 5 To: Finite Field of size 5 then Lifting map: From: Finite Field of size 5 To: Integer Ring sage: t = K.gen() sage: g(f(1,3,reduce=False)) 2 sage: g(t) Traceback (most recent call last): ... ValueError: not constant sage: g(1/t) Traceback (most recent call last): ... ValueError: not integral """
cdef inline bint normalize(nmod_poly_t numer, nmod_poly_t denom, long p): """ Puts numer/denom into a normal form: denominator monic and sharing no common factor with the numerator.
The normalized form of 0 is 0/1.
Returns True if numer and denom were changed. """ cdef long a cdef bint changed else: cdef nmod_poly_t g # Divide knowing divisible by? Can we get these quotients as a byproduct of the gcd? finally: nmod_poly_clear(g)
cdef inline unsigned long nmod_poly_leading(nmod_poly_t poly): """ Returns the leading coefficient of ``poly``. """
cdef inline void nmod_poly_inc(nmod_poly_t poly, bint monic): """ Sets poly to the "next" polynomial: this is just counting in base p.
If monic is True then will only iterate through monic polynomials. """ cdef long n cdef long a else:
cdef inline long nmod_poly_cmp(nmod_poly_t a, nmod_poly_t b): """ Compares `a` and `b`, returning 0 if they are equal.
- If the degree of `a` is less than that of `b`, returns -1.
- If the degree of `b` is less than that of `a`, returns 1.
- Otherwise, compares `a` and `b` lexicographically, starting at the leading terms. """
cdef bint nmod_poly_sqrt_check(nmod_poly_t poly): """ Quick check to see if poly could possibly be a square. """ # We could use Sage's jacobi_int which is for 32 bits integers rather # than FLINT's n_jacobi which is for longs as the FpT class is crafted # for primes 2 < p < 2^16
""" Used for pickling.
TESTS::
sage: from sage.rings.fraction_field_FpT import unpickle_FpT_element sage: R.<t> = GF(13)['t'] sage: unpickle_FpT_element(Frac(R), t+1, t) (t + 1)/t """
# Somehow this isn't in FLINT, evidently. It could be moved # elsewhere at some point. cdef int sage_cmp_nmod_poly_t(nmod_poly_t L, nmod_poly_t R): """ Compare two nmod_poly_t in a Pythonic way, so this returns -1, 0, or 1, and is consistent. """ cdef int j cdef Py_ssize_t i
# First compare the degrees
# Same degree, so compare coefficients, term by term
# Two polynomials are equal |