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
""" This linkage file implements the API for unramified extensions of the padics using FLINT's fmpz_poly_t.
AUTHORS:
- David Roe, Julian Rueth (2013-03-21) -- initial version
""" #***************************************************************************** # Copyright (C) 2013 David Roe <roed.math@gmail.com> # Julian Rueth <julian.rueth@fsfe.org> # # Distributed under the terms of the GNU General Public License (GPL) # as published by the Free Software Foundation; either version 2 of # the License, or (at your option) any later version. # http://www.gnu.org/licenses/ #*****************************************************************************
from cysignals.signals cimport sig_on, sig_off from cpython.list cimport PyList_Check, PyList_New, PyList_Append
from sage.ext.stdsage cimport PY_NEW
from sage.rings.padics.common_conversion cimport cconv_mpz_t_out_shared, cconv_mpz_t_shared, cconv_mpq_t_out_shared, cconv_mpq_t_shared, cconv_shared
from sage.rings.integer cimport Integer from sage.rings.rational cimport Rational from sage.rings.padics.padic_generic_element cimport pAdicGenericElement from sage.rings.finite_rings.integer_mod cimport IntegerMod_abstract from sage.rings.finite_rings.integer_mod_ring import Zmod
from sage.libs.flint.fmpz cimport * from sage.libs.flint.fmpz_poly cimport *
cdef inline int cconstruct(celement value, PowComputer_ prime_pow) except -1: """ Construct a new element.
INPUT:
- ``unit`` -- an ``celement`` to be initialized. - ``prime_pow`` -- the PowComputer for the ring. """
cdef inline int cdestruct(celement value, PowComputer_ prime_pow) except -1: """ Deallocate an element.
INPUT:
- ``unit`` -- an ``celement`` to be cleared. - ``prime_pow`` -- the PowComputer for the ring. """
cdef inline int ccmp(celement a, celement b, long prec, bint reduce_a, bint reduce_b, PowComputer_ prime_pow) except -2: """ Comparison of two elements.
INPUT:
- ``a`` -- an ``celement``. - ``b`` -- an ``celement``. - ``prec`` -- a long, the precision of the comparison. - ``reduce_a`` -- a bint, whether ``a`` needs to be reduced. - ``reduce_b`` -- a bint, whether ``b`` needs to be reduced. - ``prime_pow`` -- the PowComputer for the ring.
OUTPUT:
- If neither ``a`` nor ``b`` needs to be reduced, returns -1 (if `a < b`), 0 (if `a == b`) or 1 (if `a > b`)
- If at least one needs to be reduced, returns 0 (if ``a == b mod p^prec``) or 1 (otherwise) """
return 0
cdef long cmp cdef long i assert False
cdef inline int cneg(celement out, celement a, long prec, PowComputer_ prime_pow) except -1: """ Negation
Note that no reduction is performed.
INPUT:
- ``out`` -- an ``celement`` to store the negation. - ``a`` -- an ``celement`` to be negated. - ``prec`` -- a long, the precision: ignored. - ``prime_pow`` -- the PowComputer for the ring. """
cdef inline int cadd(celement out, celement a, celement b, long prec, PowComputer_ prime_pow) except -1: """ Addition
Note that no reduction is performed.
INPUT:
- ``out`` -- an ``celement`` to store the sum. - ``a`` -- an ``celement``, the first summand. - ``b`` -- an ``celement``, the second summand. - ``prec`` -- a long, the precision: ignored. - ``prime_pow`` -- the PowComputer for the ring. """
cdef inline bint creduce(celement out, celement a, long prec, PowComputer_ prime_pow) except -1: """ Reduce modulo a power of the maximal ideal.
INPUT:
- ``out`` -- an ``celement`` to store the reduction. - ``a`` -- the element to be reduced. - ``prec`` -- a long, the precision to reduce modulo. - ``prime_pow`` -- the PowComputer for the ring.
OUTPUT:
- returns True if the reduction is zero; False otherwise. """
cdef inline bint creduce_small(celement out, celement a, long prec, PowComputer_ prime_pow) except -1: """ Reduce modulo a power of the maximal ideal.
This function assumes that at most one addition/subtraction has happened on reduced inputs. For integral inputs this translates to the assumption that `-p^prec < a < 2p^prec`.
INPUT:
- ``out`` -- an ``celement`` to store the reduction. - ``a`` -- the element to be reduced. - ``prec`` -- a long, the precision to reduce modulo. - ``prime_pow`` -- the PowComputer for the ring.
OUTPUT:
- returns True if the reduction is zero; False otherwise. """
cdef inline long cremove(celement out, celement a, long prec, PowComputer_ prime_pow) except -1: """ Extract the maximum power of the uniformizer dividing this element.
INPUT:
- ``out`` -- an ``celement`` to store the unit. - ``a`` -- the element whose valuation and unit are desired. - ``prec`` -- a long, used if `a = 0`. - ``prime_pow`` -- the PowComputer for the ring.
OUTPUT:
- if `a = 0`, returns prec (the value of ``out`` is undefined). Otherwise, returns the number of times `p` divides `a`. """ else:
cdef inline long cvaluation(celement a, long prec, PowComputer_ prime_pow) except -1: """ Returns the maximum power of the uniformizer dividing this element.
This function differs from :meth:`cremove` in that the unit is discarded.
INPUT:
- ``a`` -- the element whose valuation is desired. - ``prec`` -- a long, used if `a = 0`. - ``prime_pow`` -- the PowComputer for the ring.
OUTPUT:
- if `a = 0`, returns prec. Otherwise, returns the number of times p divides a. """ cdef long val cdef long i
cdef inline bint cisunit(celement a, PowComputer_ prime_pow) except -1: """ Returns whether this element has valuation zero.
INPUT:
- ``a`` -- the element to test. - ``prime_pow`` -- the PowComputer for the ring.
OUTPUT:
- returns True if `a` has valuation 0, and False otherwise. """
cdef inline int cshift(celement out, celement a, long n, long prec, PowComputer_ prime_pow, bint reduce_afterward) except -1: """ Mulitplies by a power of the uniformizer.
INPUT:
- ``out`` -- an ``celement`` to store the result. If `n >= 0` then out will be set to `a * p^n`. If `n < 0`, out will be set to `a // p^-n`. - ``a`` -- the element to shift. - ``n`` -- long, the amount to shift by. - ``prec`` -- long, a precision modulo which to reduce. - ``prime_pow`` -- the PowComputer for the ring. - ``reduce_afterward`` -- whether to reduce afterward. """ else:
cdef inline int cshift_notrunc(celement out, celement a, long n, long prec, PowComputer_ prime_pow) except -1: """ Mulitplies by a power of the uniformizer, assuming that the valuation of a is at least -n.
INPUT:
- ``out`` -- an ``celement`` to store the result. If `n >= 0` then out will be set to `a * p^n`. If `n < 0`, out will be set to `a // p^-n`. - ``a`` -- the element to shift. Assumes that the valuation of a is at least -n. - ``n`` -- long, the amount to shift by. - ``prec`` -- long, a precision modulo which to reduce. - ``prime_pow`` -- the PowComputer for the ring. """ fmpz_poly_scalar_mul_fmpz(out, a, prime_pow.pow_fmpz_t_tmp(n)[0]) else: fmpz_poly_set(out, a)
cdef inline int csub(celement out, celement a, celement b, long prec, PowComputer_ prime_pow) except -1: """ Subtraction.
Note that no reduction is performed.
INPUT:
- ``out`` -- an ``celement`` to store the difference. - ``a`` -- an ``celement``, the first input. - ``b`` -- an ``celement``, the second input. - ``prec`` -- a long, the precision: ignored. - ``prime_pow`` -- the PowComputer for the ring. """
cdef inline int cinvert(celement out, celement a, long prec, PowComputer_ prime_pow) except -1: """ Inversion
The result will be reduced modulo p^prec.
INPUT:
- ``out`` -- an ``celement`` to store the inverse. - ``a`` -- an ``celement``, the element to be inverted. - ``prec`` -- a long, the precision. - ``prime_pow`` -- the PowComputer for the ring. """
finally:
cdef inline int cmul(celement out, celement a, celement b, long prec, PowComputer_ prime_pow) except -1: """ Multiplication.
Note that no reduction is performed.
INPUT:
- ``out`` -- an ``celement`` to store the product. - ``a`` -- an ``celement``, the first input. - ``b`` -- an ``celement``, the second input. - ``prec`` -- a long, the precision: ignored. - ``prime_pow`` -- the PowComputer for the ring. """
cdef inline int cdivunit(celement out, celement a, celement b, long prec, PowComputer_ prime_pow) except -1: """ Division.
The inversion is performed modulo p^prec. Note that no reduction is performed after the product.
INPUT:
- ``out`` -- an ``celement`` to store the quotient. - ``a`` -- an ``celement``, the first input. - ``b`` -- an ``celement``, the second input. - ``prec`` -- a long, the precision. - ``prime_pow`` -- the PowComputer for the ring. """
cdef inline int csetone(celement out, PowComputer_ prime_pow) except -1: """ Sets to 1.
INPUT:
- ``out`` -- the ``celement`` in which to store 1. - ``prime_pow`` -- the PowComputer for the ring. """
cdef inline int csetzero(celement out, PowComputer_ prime_pow) except -1: """ Sets to 0.
INPUT:
- ``out`` -- the ``celement`` in which to store 0. - ``prime_pow`` -- the PowComputer for the ring. """
cdef inline bint cisone(celement a, PowComputer_ prime_pow) except -1: """ Returns whether this element is equal to 1.
INPUT:
- ``a`` -- the element to test. - ``prime_pow`` -- the PowComputer for the ring.
OUTPUT:
- returns True if `a = 1`, and False otherwise. """ return fmpz_poly_is_one(a)
cdef inline bint ciszero(celement a, PowComputer_ prime_pow) except -1: """ Returns whether this element is equal to 0.
INPUT:
- ``a`` -- the element to test. - ``prime_pow`` -- the PowComputer for the ring.
OUTPUT:
- returns True if `a = 0`, and False otherwise. """
cdef inline int cpow(celement out, celement a, mpz_t n, long prec, PowComputer_ prime_pow) except -1: """ Exponentiation.
INPUT:
- ``out`` -- the ``celement`` in which to store the result. - ``a`` -- the base. - ``n`` -- an ``mpz_t``, the exponent. - ``prec`` -- a long, the working absolute precision. - ``prime_pow`` -- the PowComputer for the ring. """ raise NotImplementedError("negative exponent") else:
cdef inline int ccopy(celement out, celement a, PowComputer_ prime_pow) except -1: """ Copying.
INPUT:
- ``out`` -- the ``celement`` to store the result. - ``a`` -- the element to copy. - ``prime_pow`` -- the PowComputer for the ring. """
cdef inline cpickle(celement a, PowComputer_ prime_pow): """ Serialization into objects that Sage knows how to pickle.
INPUT:
- ``a`` the element to pickle. - ``prime_pow`` the PowComputer for the ring.
OUTPUT:
- a serializable object storing ``a``. """
cdef inline int cunpickle(celement out, x, PowComputer_ prime_pow) except -1: """ Reconstruction from the output of :meth:`cpickle`.
INPUT:
- ``out`` -- the ``celement`` in which to store the result. - ``x`` -- the result of :meth:`cpickle`. - ``prime_pow`` -- the PowComputer for the ring. """
cdef inline long chash(celement a, long ordp, long prec, PowComputer_ prime_pow) except -1: """ Hashing.
INPUT:
- ``a`` -- an ``celement`` storing the underlying element to hash. - ``ordp`` -- a long storing the valuation. - ``prec`` -- a long storing the precision. - ``prime_pow`` -- a PowComputer for the ring. """
# the expansion_mode enum is defined in padic_template_element_header.pxi cdef inline cexpansion_next(fmpz_poly_t value, expansion_mode mode, long curpower, PowComputer_ prime_pow): """ Return the next digit in a `p`-adic expansion of ``value``.
INPUT:
- ``value`` -- the `p`-adic element whose expansion is desired. - ``mode`` -- either ``simple_mode`` or ``smallest_mode`` - ``curpower`` -- the current power of `p` for which the coefficient is being found. Only used in ``smallest_mode``. - ``prime_pow`` -- A ``PowComputer`` holding `p`-adic data. """ cdef fmpz* c cdef long i cdef Integer digit
cdef inline cexpansion_getitem(fmpz_poly_t value, long m, PowComputer_ prime_pow): """ Return the `m`th `p`-adic digit in the ``simple_mode`` expansion.
INPUT:
- ``value`` -- the `p`-adic element whose expansion is desired. - ``m`` -- a non-negative integer: which entry in the `p`-adic expansion to return. - ``prime_pow`` -- A ``PowComputer`` holding `p`-adic data. """ cdef fmpz* c cdef long i cdef Integer digit else:
# The element is filled in for zero in the p-adic expansion if necessary. _expansion_zero = []
cdef list ccoefficients(celement x, long valshift, long prec, PowComputer_ prime_pow): """ Return a list of coefficients, as elements that can be converted into the base ring.
INPUT:
- ``x`` -- a ``celement`` giving the underlying `p`-adic element, or possibly its unit part. - ``valshift`` -- a long giving the power of the uniformizer to shift `x` by. - ``prec`` -- a long, the (relative) precision desired, used in rational reconstruction - ``prime_pow`` -- the ``PowComputer`` of the ring """ cdef Integer ansz cdef Rational ansq cdef long i else: ansq = Rational.__new__(Rational) fmpz_poly_get_coeff_mpz(mpq_numref(ansq.value), x, i) mpz_set(mpq_denref(ansq.value), prime_pow.pow_mpz_t_tmp(-valshift)) mpq_canonicalize(ansq.value) ans.append(ansq)
cdef int cteichmuller(celement out, celement value, long prec, PowComputer_ prime_pow) except -1: """ Teichmuller lifting.
INPUT:
- ``out`` -- an ``celement`` which is set to a `q-1` root of unity congruent to `value` mod `\pi`; or 0 if `a \equiv 0 \pmod{\pi}`. - ``value`` -- an ``celement``, the element mod `\pi` to lift. - ``prec`` -- a long, the precision to which to lift. - ``prime_pow`` -- the ``PowComputer`` of the ring.
ALGORITHM:
We use Hensel lifting to solve the equation `f(T)=T^q-T`. Instead of dividing by the derivative of `f`, we divide by `( q - 1 )` whose first digits coincide with `f'`. This does probably not yield quadratic convergence but taking inverses would be much more expensive than what is done here.
"""
return 0
# fmpz_ctm = 1 / (1 - q) (mod p^prec) # poly_ctm = out + fmpz_ctm*(out^q - out) # break if out == poly_ctm # out = poly_ctm
cdef int cconv(celement out, x, long prec, long valshift, PowComputer_ prime_pow) except -2: """ Conversion from other Sage types.
INPUT:
- ``out`` -- an ``celement`` to store the output.
- ``x`` -- a Sage element that can be converted to a `p`-adic element.
- ``prec`` -- a long, giving the precision desired: absolute if `valshift = 0`, relative if `valshift != 0`.
- ``valshift`` -- the power of the uniformizer to divide by before storing the result in ``out``.
- ``prime_pow`` -- a PowComputer for the ring. """ cdef long i cdef long degree
elif degree == 0: else: raise ValueError else:
cdef inline long cconv_mpq_t(celement out, mpq_t x, long prec, bint absolute, PowComputer_ prime_pow) except? -10000: """ A fast pathway for conversion of rationals that doesn't require precomputation of the valuation.
INPUT:
- ``out`` -- an ``celement`` to store the output. - ``x`` -- an ``mpq_t`` giving the integer to be converted. - ``prec`` -- a long, giving the precision desired: absolute or relative depending on the ``absolute`` input. - ``absolute`` -- if False then extracts the valuation and returns it, storing the unit in ``out``; if True then just reduces ``x`` modulo the precision. - ``prime_pow`` -- a PowComputer for the ring.
OUTPUT:
- If ``absolute`` is False then returns the valuation that was extracted (``maxordp`` when `x = 0`). """ cdef long val
cdef inline int cconv_mpq_t_out(mpq_t out, celement x, long valshift, long prec, PowComputer_ prime_pow) except -1: """ Converts the underlying `p`-adic element into a rational
- ``out`` -- gives a rational approximating the input. Currently uses rational reconstruction but may change in the future to use a more naive method - ``x`` -- an ``celement`` giving the underlying `p`-adic element - ``valshift`` -- a long giving the power of `p` to shift `x` by -` ``prec`` -- a long, the precision of ``x``, used in rational reconstruction - ``prime_pow`` -- a PowComputer for the ring """ raise ValueError mpz_set_ui(prime_pow.mpz_cconv, 0) else:
cdef inline long cconv_mpz_t(celement out, mpz_t x, long prec, bint absolute, PowComputer_ prime_pow) except -2: """ A fast pathway for conversion of integers that doesn't require precomputation of the valuation.
INPUT:
- ``out`` -- an ``celement`` to store the output. - ``x`` -- an ``mpz_t`` giving the integer to be converted. - ``prec`` -- a long, giving the precision desired: absolute or relative depending on the ``absolute`` input. - ``absolute`` -- if False then extracts the valuation and returns it, storing the unit in ``out``; if True then just reduces ``x`` modulo the precision. - ``prime_pow`` -- a PowComputer for the ring.
OUTPUT:
- If ``absolute`` is False then returns the valuation that was extracted (``maxordp`` when `x = 0`). """ cdef long val
cdef inline int cconv_mpz_t_out(mpz_t out, celement x, long valshift, long prec, PowComputer_ prime_pow) except -1: """ Converts the underlying `p`-adic element into an integer if possible.
- ``out`` -- stores the resulting integer as an integer between 0 and `p^{prec + valshift}`. - ``x`` -- an ``celement`` giving the underlying `p`-adic element. - ``valshift`` -- a long giving the power of `p` to shift `x` by. -` ``prec`` -- a long, the precision of ``x``: currently not used. - ``prime_pow`` -- a PowComputer for the ring. """ raise ValueError mpz_set_ui(prime_pow.mpz_cconv, 0) else:
## Extra functions ##
cdef cmatrix_mod_pn(celement a, long aprec, long valshift, PowComputer_ prime_pow): """ Returns the matrix of right multiplication by the element on the power basis `1, x, x^2, \ldots, x^{d-1}` for this extension field. Thus the *rows* of this matrix give the images of each of the `x^i`. The entries of the matrices are IntegerMod elements, defined modulo ``p^(self.absprec() / e)``. """ cdef int fail cdef IntegerMod_abstract item |