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
""" `p`-Adic ``ZZ_pX`` CR Element
This file implements elements of Eisenstein and unramified extensions of `\mathbb{Z}_p` and `\mathbb{Q}_p` with capped relative precision.
For the parent class see padic_extension_leaves.pyx.
The underlying implementation is through NTL's ``ZZ_pX`` class. Each element contains the following data:
- ``ordp`` (``long``) -- A power of the uniformizer to scale the unit by. For unramified extensions this uniformizer is `p`, for Eisenstein extensions it is not. A value equal to the maximum value of a long indicates that the element is an exact zero.
- ``relprec`` (``long``) -- A signed integer giving the precision to which this element is defined. For nonzero ``relprec``, the absolute value gives the power of the uniformizer modulo which the unit is defined. A positive value indicates that the element is normalized (ie ``unit`` is actually a unit: in the case of Eisenstein extensions the constant term is not divisible by `p`, in the case of unramified extensions that there is at least one coefficient that is not divisible by `p`). A negative value indicates that the element may or may not be normalized. A zero value indicates that the element is zero to some precision. If so, ``ordp`` gives the absolute precision of the element. If ``ordp`` is greater than ``maxordp``, then the element is an exact zero.
- ``unit`` (``ZZ_pX_c``) -- An ntl ``ZZ_pX`` storing the unit part. The variable `x` is the uniformizer in the case of Eisenstein extensions. If the element is not normalized, the ``unit`` may or may not actually be a unit. This ``ZZ_pX`` is created with global ntl modulus determined by the absolute value of ``relprec``. If ``relprec`` is 0, ``unit`` **is not initialized**, or destructed if normalized and found to be zero. Otherwise, let `r` be relprec and `e` be the ramification index over `\mathbb{Q}_p` or `\mathbb{Z}_p`. Then the modulus of unit is given by `p^{ceil(r/e)}`. Note that all kinds of problems arise if you try to mix moduli. ``ZZ_pX_conv_modulus`` gives a semi-safe way to convert between different moduli without having to pass through ``ZZX``.
- ``prime_pow`` (some subclass of ``PowComputer_ZZ_pX``) -- a class, identical among all elements with the same parent, holding common data.
+ ``prime_pow.deg`` -- The degree of the extension
+ ``prime_pow.e`` -- The ramification index
+ ``prime_pow.f`` -- The inertia degree
+ ``prime_pow.prec_cap`` -- the unramified precision cap. For Eisenstein extensions this is the smallest power of p that is zero.
+ ``prime_pow.ram_prec_cap`` -- the ramified precision cap. For Eisenstein extensions this will be the smallest power of `x` that is indistinguishable from zero.
+ ``prime_pow.pow_ZZ_tmp``, prime_pow.pow_mpz_t_tmp``, ``prime_pow.pow_Integer`` -- functions for accessing powers of `p`. The first two return pointers. See ``sage/rings/padics/pow_computer_ext`` for examples and important warnings.
+ ``prime_pow.get_context``, ``prime_pow.get_context_capdiv``, ``prime_pow.get_top_context`` -- obtain an ``ntl_ZZ_pContext_class`` corresponding to `p^n`. The capdiv version divides by ``prime_pow.e`` as appropriate. ``top_context`` corresponds to `p^{prec_cap}`.
+ ``prime_pow.restore_context``, ``prime_pow.restore_context_capdiv``, ``prime_pow.restore_top_context`` -- restores the given context.
+ ``prime_pow.get_modulus``, ``get_modulus_capdiv``, ``get_top_modulus`` -- Returns a ``ZZ_pX_Modulus_c*`` pointing to a polynomial modulus defined modulo `p^n` (appropriately divided by ``prime_pow.e`` in the capdiv case).
EXAMPLES:
An Eisenstein extension::
sage: R = Zp(5,5) sage: S.<x> = R[] sage: f = x^5 + 75*x^3 - 15*x^2 +125*x - 5 sage: W.<w> = R.ext(f); W Eisenstein Extension in w defined by x^5 + 75*x^3 - 15*x^2 + 125*x - 5 with capped relative precision 25 over 5-adic Ring sage: z = (1+w)^5; z 1 + w^5 + w^6 + 2*w^7 + 4*w^8 + 3*w^10 + w^12 + 4*w^13 + 4*w^14 + 4*w^15 + 4*w^16 + 4*w^17 + 4*w^20 + w^21 + 4*w^24 + O(w^25) sage: y = z >> 1; y w^4 + w^5 + 2*w^6 + 4*w^7 + 3*w^9 + w^11 + 4*w^12 + 4*w^13 + 4*w^14 + 4*w^15 + 4*w^16 + 4*w^19 + w^20 + 4*w^23 + O(w^24) sage: y.valuation() 4 sage: y.precision_relative() 20 sage: y.precision_absolute() 24 sage: z - (y << 1) 1 + O(w^25) sage: (1/w)^12+w w^-12 + w + O(w^13) sage: (1/w).parent() Eisenstein Extension in w defined by x^5 + 75*x^3 - 15*x^2 + 125*x - 5 with capped relative precision 25 over 5-adic Field
Unramified extensions::
sage: g = x^3 + 3*x + 3 sage: A.<a> = R.ext(g) sage: z = (1+a)^5; z (2*a^2 + 4*a) + (3*a^2 + 3*a + 1)*5 + (4*a^2 + 3*a + 4)*5^2 + (4*a^2 + 4*a + 4)*5^3 + (4*a^2 + 4*a + 4)*5^4 + O(5^5) sage: z - 1 - 5*a - 10*a^2 - 10*a^3 - 5*a^4 - a^5 O(5^5) sage: y = z >> 1; y (3*a^2 + 3*a + 1) + (4*a^2 + 3*a + 4)*5 + (4*a^2 + 4*a + 4)*5^2 + (4*a^2 + 4*a + 4)*5^3 + O(5^4) sage: 1/a (3*a^2 + 4) + (a^2 + 4)*5 + (3*a^2 + 4)*5^2 + (a^2 + 4)*5^3 + (3*a^2 + 4)*5^4 + O(5^5) sage: FFp = R.residue_field() sage: R(FFp(3)) 3 + O(5) sage: QQq.<zz> = Qq(25,4) sage: QQq(FFp(3)) 3 + O(5) sage: FFq = QQq.residue_field(); QQq(FFq(3)) 3 + O(5) sage: zz0 = FFq.gen(); QQq(zz0^2) (zz + 3) + O(5)
Different printing modes::
sage: R = Zp(5, print_mode='digits'); S.<x> = R[]; f = x^5 + 75*x^3 - 15*x^2 + 125*x -5; W.<w> = R.ext(f) sage: z = (1+w)^5; repr(z) '...4110403113210310442221311242000111011201102002023303214332011214403232013144001400444441030421100001' sage: R = Zp(5, print_mode='bars'); S.<x> = R[]; g = x^3 + 3*x + 3; A.<a> = R.ext(g) sage: z = (1+a)^5; repr(z) '...[4, 4, 4]|[4, 4, 4]|[4, 4, 4]|[4, 4, 4]|[4, 4, 4]|[4, 4, 4]|[4, 4, 4]|[4, 4, 4]|[4, 4, 4]|[4, 4, 4]|[4, 4, 4]|[4, 4, 4]|[4, 4, 4]|[4, 4, 4]|[4, 4, 4]|[4, 4, 4]|[4, 4, 4]|[4, 3, 4]|[1, 3, 3]|[0, 4, 2]' sage: R = Zp(5, print_mode='terse'); S.<x> = R[]; f = x^5 + 75*x^3 - 15*x^2 + 125*x -5; W.<w> = R.ext(f) sage: z = (1+w)^5; z 6 + 95367431640505*w + 25*w^2 + 95367431640560*w^3 + 5*w^4 + O(w^100) sage: R = Zp(5, print_mode='val-unit'); S.<x> = R[]; f = x^5 + 75*x^3 - 15*x^2 + 125*x -5; W.<w> = R.ext(f) sage: y = (1+w)^5 - 1; y w^5 * (2090041 + 19073486126901*w + 1258902*w^2 + 674*w^3 + 16785*w^4) + O(w^100)
You can get at the underlying ntl unit::
sage: z._ntl_rep() [6 95367431640505 25 95367431640560 5] sage: y._ntl_rep() [2090041 19073486126901 1258902 674 16785] sage: y._ntl_rep_abs() ([5 95367431640505 25 95367431640560 5], 0)
.. NOTE::
If you get an error ``internal error: can't grow this _ntl_gbigint,`` it indicates that moduli are being mixed inappropriately somewhere.
For example, when calling a function with a ``ZZ_pX_c`` as an argument, it copies. If the modulus is not set to the modulus of the ``ZZ_pX_c``, you can get errors.
AUTHORS:
- David Roe (2008-01-01): initial version
- Robert Harron (2011-09): fixes/enhancements
- Julian Rueth (2014-05-09): enable caching through ``_cache_key``
"""
#***************************************************************************** # Copyright (C) 2008 David Roe <roed.math@gmail.com> # William Stein <wstein@gmail.com> # 2014 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 __future__ import print_function
from cysignals.signals cimport sig_on, sig_off from sage.ext.stdsage cimport PY_NEW include "sage/libs/ntl/decl.pxi"
from sage.rings.integer cimport Integer from sage.rings.rational cimport Rational from sage.libs.gmp.mpz cimport * from sage.libs.gmp.mpq cimport * from sage.libs.ntl.ntl_ZZX cimport ntl_ZZX from sage.libs.ntl.ntl_ZZ cimport ntl_ZZ from sage.libs.ntl.ntl_ZZ_p cimport ntl_ZZ_p from sage.libs.ntl.ntl_ZZ_pContext cimport ntl_ZZ_pContext_class from sage.libs.ntl.ntl_ZZ_pContext import ntl_ZZ_pContext from sage.rings.padics.padic_generic_element cimport pAdicGenericElement from sage.libs.pari.all import pari_gen from sage.interfaces.gp import GpElement from sage.rings.finite_rings.integer_mod import is_IntegerMod from sage.rings.padics.padic_ext_element cimport pAdicExtElement from sage.rings.padics.precision_error import PrecisionError
from sage.rings.padics.pow_computer_ext cimport PowComputer_ZZ_pX from sage.rings.padics.pow_computer_ext cimport PowComputer_ZZ_pX_small_Eis from sage.rings.padics.pow_computer_ext cimport PowComputer_ZZ_pX_big_Eis from sage.rings.finite_rings.integer_mod_ring import IntegerModRing from sage.rings.padics.unramified_extension_generic import UnramifiedExtensionGeneric from sage.misc.superseded import deprecated_function_alias, deprecation
from sage.rings.real_double cimport RealDoubleElement
cdef object infinity from sage.rings.infinity import infinity
cdef long maxordp = (1L << (sizeof(long) * 8 - 2)) -1 cdef long minusmaxordp = -maxordp
cdef inline int check_ordp(long a) except -1: raise ValueError("valuation overflow")
cdef class pAdicZZpXCRElement(pAdicZZpXElement): def __init__(self, parent, x, absprec = infinity, relprec = infinity, empty = False): """ Creates an element of a capped relative precision, unramified or Eisenstein extension of `\mathbb{Z}_p` or `\mathbb{Q}_p`.
INPUT:
- ``parent`` -- either an ``EisensteinRingCappedRelative`` or ``UnramifiedRingCappedRelative``
- ``x`` -- an integer, rational, `p`-adic element, polynomial, list, integer_mod, pari int/frac/poly_t/pol_mod, an ``ntl_ZZ_pX``, an ``ntl_ZZ``, an ``ntl_ZZ_p``, an ``ntl_ZZX``, or something convertible into parent.residue_field()
- ``absprec`` -- an upper bound on the absolute precision of the element created
- ``relprec`` -- an upper bound on the relative precision of the element created
- ``empty`` -- whether to return after initializing to zero (without setting the valuation).
EXAMPLES::
sage: R = Zp(5,5) sage: S.<x> = R[] sage: f = x^5 + 75*x^3 - 15*x^2 +125*x - 5 sage: W.<w> = R.ext(f) sage: z = (1+w)^5; z # indirect doctest 1 + w^5 + w^6 + 2*w^7 + 4*w^8 + 3*w^10 + w^12 + 4*w^13 + 4*w^14 + 4*w^15 + 4*w^16 + 4*w^17 + 4*w^20 + w^21 + 4*w^24 + O(w^25) sage: W(pari('3 + O(5^3)')) 3 + O(w^15) sage: W(R(3,3)) 3 + O(w^15) sage: W.<w> = R.ext(x^625 + 915*x^17 - 95) sage: W(3) 3 + O(w^3125) sage: W(w, 14) w + O(w^14)
TESTS:
Check that :trac:`3865` is fixed::
sage: W(gp('3 + O(5^10)')) 3 + O(w^3125)
Check that :trac:`13612` has been fixed::
sage: R = Zp(3) sage: S.<a> = R[] sage: W.<a> = R.extension(a^2+1) sage: W(W.residue_field().zero()) O(3)
sage: K = Qp(3) sage: S.<a> = K[] sage: L.<a> = K.extension(a^2+1) sage: L(L.residue_field().zero()) O(3)
""" cdef long aprec, rprec, ctx_prec, ltmp relprec = Integer(relprec) else: rprec = 0 absprec = infinity else: cdef mpz_t tmp cdef ZZ_c tmp_z cdef Py_ssize_t i cdef Integer tmp_Int cdef Rational xlift raise ValueError("element has negative valuation") else: raise TypeError("Cannot coerce a pari p-adic with the wrong prime.") x = Rational(x) # This code doesn't check to see if the primes are the same. L = [] x = x.lift().lift() for i from 0 <= i <= x.poldegree(): L.append(Integer(x.polcoeff(i))) x = L else: mpz_init(tmp) ctx_prec = mpz_remove(tmp, (<Integer>x.modulus()).value, self.prime_pow.prime.value) if mpz_cmp_ui(tmp, 1) == 0: mpz_clear(tmp) x = x.lift() if absprec is infinity or ctx_prec < aprec: aprec = ctx_prec absprec = 0 # absprec just has to be non-infinite: everything else uses aprec else: mpz_clear(tmp) raise TypeError("cannot coerce from the given integer mod ring (not a power of the same prime)") ctx_prec = ZZ_remove(tmp_z, (<ntl_ZZ>x.modulus()).x, self.prime_pow.pow_ZZ_tmp(1)[0]) if ZZ_IsOne(tmp_z): x = x.lift() tmp_Int = PY_NEW(Integer) ZZ_to_mpz(tmp_Int.value, &(<ntl_ZZ>x).x) x = tmp_Int if absprec is infinity or ctx_prec < aprec: aprec = ctx_prec absprec = 0 # absprec just has to be non-infinite: everything else uses aprec else: raise TypeError("cannot coerce the given ntl_ZZ_p (modulus not a power of the same prime)") tmp_Int = PY_NEW(Integer) ZZ_to_mpz(tmp_Int.value, &(<ntl_ZZ>x).x) x = tmp_Int x = Integer(x) # Should only reach here if x is not in F_p z = parent.gen() poly = x.polynomial().list() x = sum([poly[i].lift() * (z ** i) for i in range(len(poly))], parent.zero()) if absprec is infinity or 1 < aprec: aprec = 1 absprec = 0 # absprec just has to be non-infinite: everything else uses aprec cdef pAdicZZpXCRElement _x self._set_from_mpz_rel((<Integer>x).value, rprec) else: else: else: else: self._set_inexact_zero(_x.ordp) # this works for exact zeros too. else: if -_x.relprec < rprec: rprec = _x.relprec else: rprec = -rprec if absprec is infinity or aprec > _x.ordp - rprec: self._set(&_x.unit, _x.ordp, rprec) elif aprec > _x.ordp: self._set(&_x.unit, _x.ordp, _x.ordp - aprec) #negating relprec to indicate non-normalized. else: self._set_inexact_zero(aprec) else: self._set(&_x.unit, _x.ordp, rprec) else: _x._normalize() else: else: # x is a pAdicZZpXCAElement else: else: self._set_from_ZZ_pX_both(&(<ntl_ZZ_pX>poly).x,(<ntl_ZZ_pX>poly).c, aprec, rprec) elif x.parent() is parent.fraction_field(): _x = <pAdicZZpXCRElement>x if _x.relprec < 0: _x._normalize() if _x._is_exact_zero(): self._set_exact_zero() elif _x._is_inexact_zero(): self._set_inexact_zero(_x.ordp) else: if _x.relprec < rprec: rprec = _x.relprec self._set(&_x.unit, _x.ordp, rprec) else: raise NotImplementedError("Conversion from different p-adic extensions not yet supported") else: else:
def _cache_key(self): r""" Return a hashable key which identifies this element.
This makes it possible to use this element in caches such as functions or methods decorated with ``@cached_function`` or ``@cached_method`` respectively.
EXAMPLES:
In the following example, ``a`` and ``b`` compare equal. They cannot have a meaningful hash value since then their hash value would have to be the same::
sage: K.<a> = Qq(9) sage: b = a + O(3) sage: a == b True sage: hash(a) Traceback (most recent call last): ... TypeError: unhashable type: 'sage.rings.padics.qadic_flint_CR.qAdicCappedRelativeElement'
However, we want to cache computations which depend on them. Therefore they define a ``_cache_key`` which is hashable and uniquely identifies them::
sage: a._cache_key() (..., ((0, 1),), 0, 20) sage: b._cache_key() (..., ((0, 1),), 0, 1)
TESTS:
Check that zero values are handled correctly::
sage: K.zero()._cache_key() (..., 0) sage: K(0,1)._cache_key() (..., 1, 0)
""" return (self.parent(), 0, self.valuation()) else:
cdef int _set_inexact_zero(self, long absprec) except -1: """ Sets ``self`` to be zero with valuation absprec.
EXAMPLES::
sage: R = Zp(5,5) sage: S.<x> = R[] sage: f = x^5 + 75*x^3 - 15*x^2 +125*x - 5 sage: W.<w> = R.ext(f) sage: z = W(0,6); z # indirect doctest O(w^6) sage: z.valuation() 6 sage: z.precision_absolute() 6 sage: z.precision_relative() 0
TESTS::
sage: R = Zp(17, 3) sage: S.<x> = R[] sage: W.<w> = R.ext(x^34 - 289*x^5 + 17) sage: z = W(0, 6); z O(w^6) sage: z.valuation() 6 sage: z.precision_absolute() 6 sage: z.precision_relative() 0 """
cdef int _set_exact_zero(self) except -1: """ Sets ``self`` to be an exact zero.
EXAMPLES::
sage: R = Zp(5,5) sage: S.<x> = R[] sage: f = x^5 + 75*x^3 - 15*x^2 +125*x - 5 sage: W.<w> = R.ext(f) sage: z = R(0); z # indirect doctest 0 sage: z.valuation() +Infinity sage: z.precision_absolute() +Infinity sage: z.precision_relative() 0
TESTS::
sage: R = Zp(89, 3) sage: S.<x> = R[] sage: W.<w> = R.ext(x^34 - 2*89*x^5 + 89) sage: z = R(0); z # indirect doctest 0 sage: z.valuation() +Infinity sage: z.precision_absolute() +Infinity sage: z.precision_relative() 0 """
cpdef bint _is_exact_zero(self) except -1: """ Tests if ``self`` is an exact zero.
EXAMPLES::
sage: R = Qp(3,5) sage: S.<x> = R[] sage: f = x^5 + 75*x^3 - 15*x^2 +125*x - 5 sage: W.<w> = R.ext(f) sage: z = W(0) sage: z._is_exact_zero() True sage: z = W(0,6) sage: z._is_exact_zero() False
TESTS::
sage: R = Qp(53, 3) sage: S.<x> = R[] sage: W.<w> = R.ext(x^34 - 2*53^5*x^9 + 53) sage: z = W(0) sage: z._is_exact_zero() True sage: z = W(0,6) sage: z._is_exact_zero() False
""" else:
cpdef bint _is_inexact_zero(self) except -1: """ Tests if ``self`` is an inexact zero.
EXAMPLES::
sage: R = Zp(7,5) sage: S.<x> = R[] sage: f = x^5 + 75*x^3 - 15*x^2 +125*x - 5 sage: W.<w> = R.ext(f) sage: z = W(0) sage: z._is_inexact_zero() False sage: z = W(0,6) sage: z._is_inexact_zero() True
TESTS::
sage: R = Qp(29, 3) sage: S.<x> = R[] sage: W.<w> = R.ext(x^29 - 2*29^5*x - 29) sage: z = W(0) sage: z._is_inexact_zero() False sage: z = W(0,6) sage: z._is_inexact_zero() True """ else:
cdef int _set(self, ZZ_pX_c* unit, long ordp, long relprec) except -1: """ Sets ``unit``, ``ordp`` and ``relprec`` directly.
EXAMPLES::
sage: R = Zp(5,5) sage: S.<x> = R[] sage: f = x^5 + 75*x^3 - 15*x^2 +125*x - 5 sage: W.<w> = R.ext(f) sage: F = W.fraction_field() sage: z = F(1+w); z # indirect doctest 1 + w + O(w^25)
TESTS::
sage: R = Zp(17,30) sage: S.<x> = R[] sage: f = x^51 - 34 sage: W.<w> = R.ext(f) sage: F = W.fraction_field() sage: z = F(1+w); z # indirect doctest 1 + w + O(w^1530) sage: z = F(w+w^2,relprec=0); z O(w) """
cdef int _set_from_mpz_rel(self, mpz_t x, long relprec) except -1: """ Sets ``self`` from an ``mpz_t`` with relative precision bounded by ``relprec``.
EXAMPLES::
sage: R = Zp(5,5) sage: S.<x> = R[] sage: f = x^5 + 75*x^3 - 15*x^2 +125*x - 5 sage: W.<w> = R.ext(f) sage: W(70, relprec = 8) # indirect doctest 4*w^5 + 3*w^7 + w^9 + 2*w^10 + 2*w^11 + O(w^13) sage: W(70, relprec = 0) O(w^5)
TESTS::
sage: R = Qp(13,50) sage: S.<x> = R[] sage: f = x^169 - 13 sage: W.<w> = R.ext(f) sage: a = W(65, relprec = 8); a.valuation() # indirect doctest 169 sage: W(65, relprec = 0) O(w^169) """ if mpz_sgn(x) == 0: self._set_exact_zero() return 0 cdef mpz_t tmp_m cdef ZZ_c tmp_z cdef long shift mpz_init(tmp_m) sig_on() shift = mpz_remove(tmp_m, x, self.prime_pow.prime.value) sig_off() self._set_prec_rel(relprec) mpz_to_ZZ(&tmp_z, tmp_m) mpz_clear(tmp_m) if self.relprec != 0: ZZ_pX_SetCoeff(self.unit, 0, ZZ_to_ZZ_p(tmp_z)) self.ordp = 0 self._pshift_self(shift) else: self.ordp = shift * self.prime_pow.e
cdef int _set_from_mpz_both(self, mpz_t x, long absprec, long relprec) except -1: """ Sets ``self`` from an ``mpz_t`` with relative precision bounded by ``relprec`` and absolute precision bounded by ``absprec``.
EXAMPLES::
sage: R = Zp(5,5) sage: S.<x> = R[] sage: f = x^5 + 75*x^3 - 15*x^2 +125*x - 5 sage: W.<w> = R.ext(f) sage: W(70, 8) # indirect doctest 4*w^5 + 3*w^7 + O(w^8) sage: W(70, absprec = 4) O(w^4)
TESTS::
sage: R = Zp(7,3) sage: S.<x> = R[] sage: f = x^49 + 7*x^21 - 14 sage: W.<w> = R.ext(f) sage: W(70, 100) # indirect doctest 5*w^49 + 6*w^70 + 3*w^91 + O(w^100) sage: W(70, absprec = 4) O(w^4) """ self._set_inexact_zero(absprec) return 0 cdef mpz_t tmp_m cdef ZZ_c tmp_z cdef long shift # This indicates that self._set_inexact_zero was called mpz_clear(tmp_m) return 0
cdef int _set_from_mpq_rel(self, mpq_t x, long relprec) except -1: """ Sets ``self`` from an ``mpq_t`` with relative precision bounded by ``relprec``.
EXAMPLES::
sage: R = Zp(5,5) sage: S.<x> = R[] sage: f = x^5 + 75*x^3 - 15*x^2 +125*x - 5 sage: W.<w> = R.ext(f) sage: z = W(70/3, relprec = 9); z # indirect doctest 3*w^5 + w^7 + 2*w^9 + 2*w^10 + 4*w^11 + w^12 + 2*w^13 + O(w^14) sage: z * 3 4*w^5 + 3*w^7 + w^9 + 2*w^10 + 2*w^11 + w^13 + O(w^14) sage: W(70) 4*w^5 + 3*w^7 + w^9 + 2*w^10 + 2*w^11 + w^13 + 3*w^16 + w^17 + w^18 + 4*w^20 + 4*w^21 + w^22 + 2*w^23 + 3*w^25 + w^27 + O(w^30) sage: F = W.fraction_field() sage: y = F(3/700); y w^-10 + w^-8 + 4*w^-6 + w^-3 + 4*w^-2 + 3*w^-1 + 3 + 4*w + w^3 + 4*w^4 + w^5 + 4*w^6 + 2*w^7 + 3*w^8 + 4*w^9 + 3*w^10 + 4*w^11 + w^12 + O(w^15) sage: y * 700 3 + O(w^25) sage: W(70/3, relprec = 0) O(w^5) sage: c = F(5^-1 + O(5^2)); c w^-5 + 3*w^-3 + 2*w^3 + 4*w^5 + 4*w^6 + 3*w^7 + w^9 + O(w^10) sage: c * 5 1 + O(w^15)
TESTS::
sage: R = Zp(11, 8, print_mode='digits') sage: S.<x> = R[] sage: f = x^3 + 1331 * x^2 - 11 * x + 11 sage: W.<w> = R.ext(f) sage: z = W(77/3, relprec = 11); repr(z)[3:] '304107A2555000' sage: repr(z*3)[3:] '56698765444000' sage: repr(W(77))[3:] '5800A6604678856698765444000' sage: F = W.fraction_field() sage: y = F(3/847); repr(y)[3:] '5563A4105291255628.148272' sage: repr(y*847)[3:] '000000000000000000000003' sage: repr(W(77/3, relprec=0)) '0' sage: c = F(11^-1 + O(11^2)); repr(c)[3:] '011111.01A' sage: repr(c * 11)[3:] '000000001' """ cdef mpz_t num_unit, den_unit
cdef int _set_from_mpq_both(self, mpq_t x, long absprec, long relprec) except -1: """ Sets ``self`` from an ``mpq_t`` with relative precision bounded by ``relprec`` and absolute precision bounded by ``absprec``.
EXAMPLES::
sage: R = Zp(5,5) sage: S.<x> = R[] sage: f = x^5 + 75*x^3 - 15*x^2 +125*x - 5 sage: W.<w> = R.ext(f) sage: z = W(70/3, 14); z # indirect doctest 3*w^5 + w^7 + 2*w^9 + 2*w^10 + 4*w^11 + w^12 + 2*w^13 + O(w^14) sage: z * 3 4*w^5 + 3*w^7 + w^9 + 2*w^10 + 2*w^11 + w^13 + O(w^14) sage: W(70) 4*w^5 + 3*w^7 + w^9 + 2*w^10 + 2*w^11 + w^13 + 3*w^16 + w^17 + w^18 + 4*w^20 + 4*w^21 + w^22 + 2*w^23 + 3*w^25 + w^27 + O(w^30) sage: F = W.fraction_field() sage: y = F(3/700,-2); y w^-10 + w^-8 + 4*w^-6 + w^-3 + O(w^-2) sage: y * 700 3 + O(w^8) sage: W(70/3, absprec = 4) O(w^4) """ cdef mpz_t num_unit, den_unit # indicates an inexact zero
cdef int _set_from_mpq_part1(self, mpz_t num_unit, mpz_t den_unit, mpq_t x) except -1: """ Sets ``num_unit`` to be the unit of the numerator, ``den_unit`` to be the unit of the denominator and sets ``self.ordp`` correctly.
TESTS::
sage: R = Zp(5,5) sage: S.<x> = R[] sage: f = x^5 + 75*x^3 - 15*x^2 +125*x - 5 sage: W.<w> = R.ext(f) sage: z = W(7000/3, 23); z # indirect doctest 2*w^15 + 2*w^17 + 3*w^19 + w^22 + O(w^23) """ cdef long num_ordp, den_ordp mpz_clear(num_unit) mpz_clear(den_unit) raise ValueError("p divides the denominator")
cdef int _set_from_mpq_part2(self, mpz_t num_unit, mpz_t den_unit) except -1: """ Given that ``self.ordp`` and ``self.relprec`` have been set, takes ``num_unit`` and ``den_unit`` and sets ``self.unit``.
TESTS::
sage: R = Zp(5,5) sage: S.<x> = R[] sage: f = x^5 + 75*x^3 - 15*x^2 +125*x - 5 sage: W.<w> = R.ext(f) sage: W(QQ(0), 23) # indirect doctest O(w^23) sage: W(QQ(0)) 0 """ cdef ZZ_c num_zz, den_zz cdef ZZ_p_c tmp_zp cdef mpz_t tmp_m #The context has been restored in setting self.relprec
cdef int _set_from_ZZX_rel(self, ZZX_c poly, long relprec) except -1: """ Sets ``self`` from a ``ZZX`` with relative precision bounded by ``relprec``.
EXAMPLES::
sage: R = Zp(5,5) sage: S.<x> = R[] sage: f = x^5 + 75*x^3 - 15*x^2 +125*x - 5 sage: W.<w> = R.ext(f) sage: z = W(ntl.ZZX([4,1,16]), relprec = 14); z # indirect doctest 4 + w + w^2 + 3*w^7 + w^9 + 2*w^11 + 4*w^13 + O(w^14) sage: z._ntl_rep() [4 1 16] sage: z = W(ntl.ZZX([5^40,5^42,3*5^41]), relprec = 14); z w^200 + 4*w^207 + 4*w^209 + w^210 + 2*w^211 + 2*w^213 + O(w^214) sage: W(5)^40 + w*W(5)^42 + w^2 * W(3) * W(5)^41 w^200 + 4*w^207 + 4*w^209 + w^210 + 2*w^211 + 2*w^213 + 2*w^215 + w^217 + 2*w^218 + w^220 + w^221 + w^222 + 3*w^224 + O(w^225) sage: z = W(ntl.ZZX([5^40,5^42,3*5^41]), relprec = 0); z O(w^200) """ self._set_exact_zero() return 0 raise NotImplementedError # the -1 in the next line signals that there is no absprec specified # context was restored in _set_from_ZZX_part1
cdef int _set_from_ZZX_both(self, ZZX_c poly, long absprec, long relprec) except -1: """ Sets ``self`` from a ``ZZX`` with relative precision bounded by ``relprec`` and absolute precision bounded by ``absprec``.
EXAMPLES::
sage: R = Zp(5,5) sage: S.<x> = R[] sage: f = x^5 + 75*x^3 - 15*x^2 +125*x - 5 sage: W.<w> = R.ext(f) sage: z = W(ntl.ZZX([4,1,16]), 12); z # indirect doctest 4 + w + w^2 + 3*w^7 + w^9 + 2*w^11 + O(w^12) sage: z._ntl_rep() [4 1 16] sage: z = W(ntl.ZZX([5^40,5^42,3*5^41]), 212); z w^200 + 4*w^207 + 4*w^209 + w^210 + 2*w^211 + O(w^212) sage: z = W(ntl.ZZX([5^40,5^42,3*5^41]), 197); z O(w^197) """ self._set_inexact_zero(absprec) return 0 raise NotImplementedError # indicates _set_inexact_zero was called # context was restored in _set_from_ZZX_part1
cdef int _set_from_ZZX_part1(self, ZZX_c poly, long absprec, long relprec) except -1: """ Sets ``self.ordp`` from ``poly`` and restores the context. ``poly`` must have degree less than ``self.prime_pow.deg``
TESTS::
sage: R = Zp(5,5) sage: S.<x> = R[] sage: f = x^5 + 75*x^3 - 15*x^2 +125*x - 5 sage: W.<w> = R.ext(f) sage: z = W(ntl.ZZX([4,1,16]), 12); z # indirect doctest 4 + w + w^2 + 3*w^7 + w^9 + 2*w^11 + O(w^12) """ cdef long minval cdef long curval cdef ZZ_c tmp_z minval = curval mini = i else: # indicates self._set_inexact_zero was called # _set_prec_rel or both has restored the context so that part2 works.
cdef int _set_from_ZZ_pX_rel(self, ZZ_pX_c* poly, ntl_ZZ_pContext_class ctx, long relprec) except -1: """ Sets ``self`` from a ``ZZ_pX`` with relative precision bounded by ``relprec``.
If ``ctx`` is ``None`` and ``poly`` is 0 this function will raise an error (a ``ZZ_pX`` cannot represent something with infinite absolute precision).
EXAMPLES::
sage: R = Zp(5,5) sage: S.<x> = R[] sage: f = x^5 + 75*x^3 - 15*x^2 +125*x - 5 sage: W.<w> = R.ext(f) sage: z = W(ntl.ZZ_pX([4,1,16],5^2)); z # indirect doctest 4 + w + w^2 + 3*w^7 + w^9 + O(w^10) sage: z._ntl_rep() [4 1 16] sage: z = W(ntl.ZZ_pX([5^40,5^42,3*5^41], 5^44)); z w^200 + 4*w^207 + 4*w^209 + w^210 + 2*w^211 + 2*w^213 + 2*w^215 + w^217 + 2*w^218 + O(w^220) sage: z = W(ntl.ZZ_pX([5^40,5^42,3*5^41], 5^44), relprec = 0); z O(w^200) """ if ctx_prec == -1: raise ValueError("must specify either a context or an absolute precision bound") else: self._set_inexact_zero(ctx_prec) return 0 self._set_prec_rel(self.ordp + relprec) else:
cdef int _set_from_ZZ_pX_both(self, ZZ_pX_c* poly, ntl_ZZ_pContext_class ctx, long absprec, long relprec) except -1: """ Sets ``self`` from a ``ZZ_pX`` with relative precision bounded by ``relprec`` and absolute precision bounded by ``absprec``.
EXAMPLES::
sage: R = Zp(5,5) sage: S.<x> = R[] sage: f = x^5 + 75*x^3 - 15*x^2 +125*x - 5 sage: W.<w> = R.ext(f) sage: z = W(ntl.ZZ_pX([4,1,16],5^2), absprec = 8, relprec = 12); z # indirect doctest 4 + w + w^2 + 3*w^7 + O(w^8) sage: z._ntl_rep() [4 1 16] sage: z = W(ntl.ZZ_pX([5^40,5^42,3*5^41], 5^50), 220); z w^200 + 4*w^207 + 4*w^209 + w^210 + 2*w^211 + 2*w^213 + 2*w^215 + w^217 + 2*w^218 + O(w^220) sage: z = W(ntl.ZZ_pX([5^40,5^42,3*5^41], 5^44), absprec = 77); z O(w^77) """ cdef long ctx_prec absprec = ctx_prec * self.prime_pow.e self._set_inexact_zero(absprec) return 0 else:
cdef int _set_from_ZZ_pX_part1(self, ZZ_pX_c* poly) except -1: """ Sets ``self.ordp`` based on ``poly``. ``poly`` must not be 0.
TESTS::
sage: R = Zp(5,5) sage: S.<x> = R[] sage: f = x^5 + 75*x^3 - 15*x^2 +125*x - 5 sage: W.<w> = R.ext(f) sage: z = W(ntl.ZZ_pX([4,1,16],5^2), absprec = 8, relprec = 12); z # indirect doctest 4 + w + w^2 + 3*w^7 + O(w^8) """ cdef long val, index self.ordp = val else:
cdef int _set_from_ZZ_pX_part2(self, ZZ_pX_c* poly) except -1: """ Assuming that ``self.ordp`` and ``self.relprec`` have been set, sets ``self.unit`` to ``poly`` and then normalizes.
TESTS::
sage: R = Zp(5,5) sage: S.<x> = R[] sage: f = x^5 + 75*x^3 - 15*x^2 +125*x - 5 sage: W.<w> = R.ext(f) sage: z = W(ntl.ZZ_pX([4,1,16],5^2), absprec = 8, relprec = 12); z # indirect doctest 4 + w + w^2 + 3*w^7 + O(w^8) """ # We've set self.relprec to what is actually the absolute precision.
cdef bint _set_prec_rel(self, long relprec) except -1: """ Safely sets the relative precision of ``self`` to be the absolute value of ``relprec``.
Returns ``True`` iff ``self.relprec`` was reset.
Note that this will wipe out anything in ``self.unit``. Be careful resetting ``self.unit`` directly: if you set it to a different modulus, NTL may have problems. The safest way to reset ``self.unit`` to a different modulus is::
self.prime_pow.restore_context_capdiv(self.relprec) cdef ZZ_pX_c tmp = self.unit self._set_prec_rel(new_rel_prec) ZZ_pX_conv_modulus(self.unit, tmp, self.prime_pow.get_context_capdiv(self.relprec).x)
You may be able to just set ``self.relprec`` and ``ZZ_pX_conv_modulus`` if you're decreasing precision. I'm not sure.
TESTS::
sage: R = Zp(5,5) sage: S.<x> = R[] sage: f = x^5 + 75*x^3 - 15*x^2 +125*x - 5 sage: W.<w> = R.ext(f) sage: W(70, relprec = 8) # indirect doctest 4*w^5 + 3*w^7 + w^9 + 2*w^10 + 2*w^11 + O(w^13) """
cdef bint _set_prec_both(self, long absprec, long relprec) except -1: """ Assuming ``self.ordp`` is set, sets the relative precision of ``self`` to the minimum of ``abs(relprec)`` and ``absprec-self.ordp``.
If ``relprec`` is negative, will set ``self.relprec`` to be negative (indicating unnormalized unit)
Returns`` True`` iff ``self.relprec = 0``, ie ``self`` was set to an inexact zero.
Note that this will wipe out anything in ``self.unit``. Be careful resetting ``self.unit`` directly: if you set it to a different modulus, NTL may have problems. The safest way to reset ``self.unit`` to a different modulus is:
self.prime_pow.restore_context_capdiv(self.relprec) cdef ZZ_pX_c tmp = self.unit self._set_prec_rel(new_rel_prec) ZZ_pX_conv_modulus(self.unit, tmp, self.prime_pow.get_context_capdiv(self.relprec).x)
You may be able to just set ``self.relprec`` and ``ZZ_pX_conv_modulus`` if you're decreasing precision. I'm not sure.
TESTS::
sage: R = Zp(5,5) sage: S.<x> = R[] sage: f = x^5 + 75*x^3 - 15*x^2 +125*x - 5 sage: W.<w> = R.ext(f) sage: W(70, 8) # indirect doctest 4*w^5 + 3*w^7 + O(w^8) """ cdef long arelprec arelprec = -relprec else: else: self.relprec = -self.relprec
cdef int _normalize(self) except -1: """ Normalizes ``self``, adjusting ``self.ordp``, ``self.relprec``, and ``self.unit`` so that ``self.unit`` actually represents a unit.
EXAMPLES::
sage: R = Zp(5,5) sage: S.<x> = R[] sage: f = x^5 + 75*x^3 - 15*x^2 +125*x - 5 sage: W.<w> = R.ext(f) sage: z = (1+w)^5 sage: y = z - 1 sage: y._ntl_rep_unnormalized() [5 3005 25 3060 5] sage: y # indirect doctest w^5 + w^6 + 2*w^7 + 4*w^8 + 3*w^10 + w^12 + 4*w^13 + 4*w^14 + 4*w^15 + 4*w^16 + 4*w^17 + 4*w^20 + w^21 + 4*w^24 + O(w^25) sage: y._ntl_rep_unnormalized() [41 26 152 49 535] """ cdef long minval, mini, shift else: else: else:
def _is_normalized(self): """ Returns whether this element is currently normalized.
EXAMPLES::
sage: R.<a> = ZqCR(125,implementation="NTL"); b = 5*a + 4; c = 10*a^2 + 6; d = b + c sage: d._is_normalized() False sage: d.valuation() 1 sage: d._is_normalized() True """
cdef int _internal_lshift(self, long shift) except -1: """ Multiplies ``self.unit`` by ``x^shift``.
Note that ``self.relprec`` must be set before calling this function and should not be 0, and self.unit must be defined to precision ``self.relprec - shift``
This function does not alter ``self.ordp`` even though it WILL change the valuation of ``self.unit``
Also note that if you call this function you should usually manually set ``self.relprec = -self.relprec`` since this function will usually unnormalize ``self``.
TESTS::
sage: R = Zp(5,5) sage: S.<x> = R[] sage: f = x^5 + 75*x^3 - 15*x^2 +125*x - 5 sage: W.<w> = R.ext(f) sage: z = (1+w)^5 sage: y = z - 1 sage: y # indirect doctest w^5 + w^6 + 2*w^7 + 4*w^8 + 3*w^10 + w^12 + 4*w^13 + 4*w^14 + 4*w^15 + 4*w^16 + 4*w^17 + 4*w^20 + w^21 + 4*w^24 + O(w^25) """ raise ValueError("p-adic Internal l-shift called with relative precision 0") cdef ZZ_pX_c tmpP cdef ZZ_pX_Modulus_c* mod else: else:
cdef int _pshift_self(self, long shift) except -1: """ Multiplies ``self`` by ``p^shift``.
This function assumes that ``self.relprec``, ``self.ordp`` and ``self.unit`` are already set (in the case ``self.prime_pow.e != 1``), and is more reasonable to call externally than ``_internal_lshift``
EXAMPLES::
sage: R = Qp(5,5) sage: S.<x> = R[] sage: f = x^5 + 75*x^3 - 15*x^2 +125*x - 5 sage: W.<w> = R.ext(f) sage: z = W(3/25, relprec = 6); z 3*w^-10 + 3*w^-8 + 2*w^-6 + O(w^-4) sage: z * 25 3 + O(w^6) """ cdef ZZ_pX_c high_shifter, high_shifter2 cdef ZZ_pX_Modulus_c *modulus cdef ZZ_pX_Modulus_c modulus_up cdef ntl_ZZ_pContext_class c cdef PowComputer_ZZ_pX_small_Eis sm cdef PowComputer_ZZ_pX_big_Eis big cdef ntl_ZZ_pX printer cdef ZZ_pX_c* high_array cdef long i, high_length else: high_array = (<PowComputer_ZZ_pX_big_Eis>self.prime_pow).high_shifter else: raise TypeError("unrecognized PowComputer type") else: raise TypeError("unrecognized PowComputer type") # high_shifter = p^(2^(high_length - 1))/x^(e*2^(high_length - 1)) # if shift = r + s * 2^(high_length - 1) # then high_shifter = p^(s*2^(high_length - 1))/x^(e*s*2^(high_length - 1)) # Now we only need to multiply self.unit by p^r/x^(e*r) where r < 2^(high_length - 1), which is tractable.
cdef pAdicZZpXCRElement _new_c(self, long relprec): """ Returns a new element with the same parent as ``self`` and relative precision ``relprec``
Note that if ``relprec`` is non-positive, the convention is that ``relprec = 0`` indicates an exact or inexact zero, ``relprec < 0`` indicates an unnormalized element.
EXAMPLES::
sage: R = Qp(5,5) sage: S.<x> = R[] sage: f = x^5 + 75*x^3 - 15*x^2 +125*x - 5 sage: W.<w> = R.ext(f) sage: w^5 + 1 # indirect doctest 1 + w^5 + O(w^25) """ else:
def __reduce__(self): """ Pickles ``self``.
EXAMPLES::
sage: R = Qp(5,5) sage: S.<x> = R[] sage: f = x^5 + 75*x^3 - 15*x^2 +125*x - 5 sage: W.<w> = R.ext(f) sage: z = (1 + w)^5 - 1 sage: loads(dumps(z)) == z True """ cdef Integer relprec, ordp return make_ZZpXCRElement, (self.parent(), None, ordp, relprec, 0)
cdef int _cmp_units(left, pAdicGenericElement right) except -2: """ For units ``left`` and ``right``, returns 0 if they are equal up to the lesser of the two precisions, or 1 if they are not.
EXAMPLES::
sage: R = Qp(5,5) sage: S.<x> = R[] sage: f = x^5 + 75*x^3 - 15*x^2 +125*x - 5 sage: W.<w> = R.ext(f) sage: w == 1 # indirect doctest False sage: y = 1 + w + O(w^7) sage: z = 1 + w + w^10 + O(w^13) sage: y == z True """ # This function needs improvement. In particular, there are a lot of # speed improvements to be had, and it should be changed so that it # returns 1 only half the time (and -1 the other half) when left and # right are not equal. # for now, just return 1
def __invert__(self): """ Returns the inverse of ``self``.
EXAMPLES::
sage: R = Zp(5,5) sage: S.<x> = R[] sage: f = x^5 + 75*x^3 - 15*x^2 +125*x - 5 sage: W.<w> = R.ext(f) sage: z = (1 + w)^5 sage: y = ~z; y # indirect doctest 1 + 4*w^5 + 4*w^6 + 3*w^7 + w^8 + 2*w^10 + w^11 + w^12 + 2*w^14 + 3*w^16 + 3*w^17 + 4*w^18 + 4*w^19 + 2*w^20 + 2*w^21 + 4*w^22 + 3*w^23 + 3*w^24 + O(w^25) sage: y.parent() Eisenstein Extension in w defined by x^5 + 75*x^3 - 15*x^2 + 125*x - 5 with capped relative precision 25 over 5-adic Field sage: z = z - 1 sage: ~z w^-5 + 4*w^-4 + 4*w^-3 + 4*w^-2 + 2*w^-1 + 1 + w + 4*w^2 + 4*w^3 + 4*w^4 + w^5 + w^6 + w^7 + 4*w^8 + 4*w^9 + 2*w^10 + w^11 + 2*w^12 + 4*w^13 + 4*w^14 + O(w^15) sage: ~z * z 1 + O(w^20) """ raise ZeroDivisionError("cannot divide by zero") raise PrecisionError("cannot divide by something indistinguishable from zero") ZZ_pX_InvMod_newton_unram(ans.unit, self.unit, self.prime_pow.get_modulus(ans.relprec)[0], self.prime_pow.get_context(ans.relprec).x, self.prime_pow.get_context(1).x) else:
cdef pAdicZZpXCRElement _lshift_c(self, long n): """ Multiplies ``self`` by the uniformizer raised to the power ``n``. If ``n`` is negative, right shifts by ``-n``.
EXAMPLES::
sage: R = Zp(5,5) sage: S.<x> = R[] sage: f = x^5 + 75*x^3 - 15*x^2 +125*x - 5 sage: W.<w> = R.ext(f) sage: z = (1 + w)^5 sage: z 1 + w^5 + w^6 + 2*w^7 + 4*w^8 + 3*w^10 + w^12 + 4*w^13 + 4*w^14 + 4*w^15 + 4*w^16 + 4*w^17 + 4*w^20 + w^21 + 4*w^24 + O(w^25) sage: z << 17 # indirect doctest w^17 + w^22 + w^23 + 2*w^24 + 4*w^25 + 3*w^27 + w^29 + 4*w^30 + 4*w^31 + 4*w^32 + 4*w^33 + 4*w^34 + 4*w^37 + w^38 + 4*w^41 + O(w^42) sage: z << (-1) w^4 + w^5 + 2*w^6 + 4*w^7 + 3*w^9 + w^11 + 4*w^12 + 4*w^13 + 4*w^14 + 4*w^15 + 4*w^16 + 4*w^19 + w^20 + 4*w^23 + O(w^24) """ cdef pAdicZZpXCRElement ans ans = self._new_c(0) else:
def __lshift__(pAdicZZpXCRElement self, shift): """ Multiplies ``self`` by the uniformizer raised to the power ``n``. If ``n`` is negative, right shifts by ``-n``.
EXAMPLES::
sage: R = Zp(5,5) sage: S.<x> = R[] sage: f = x^5 + 75*x^3 - 15*x^2 +125*x - 5 sage: W.<w> = R.ext(f) sage: z = (1 + w)^5 sage: z 1 + w^5 + w^6 + 2*w^7 + 4*w^8 + 3*w^10 + w^12 + 4*w^13 + 4*w^14 + 4*w^15 + 4*w^16 + 4*w^17 + 4*w^20 + w^21 + 4*w^24 + O(w^25) sage: z << 17 # indirect doctest w^17 + w^22 + w^23 + 2*w^24 + 4*w^25 + 3*w^27 + w^29 + 4*w^30 + 4*w^31 + 4*w^32 + 4*w^33 + 4*w^34 + 4*w^37 + w^38 + 4*w^41 + O(w^42) sage: z << (-1) w^4 + w^5 + 2*w^6 + 4*w^7 + 3*w^9 + w^11 + 4*w^12 + 4*w^13 + 4*w^14 + 4*w^15 + 4*w^16 + 4*w^19 + w^20 + 4*w^23 + O(w^24) """ cdef pAdicZZpXCRElement ans if self._is_exact_zero(): return self if self.prime_pow.in_field or mpz_sgn((<Integer>shift).value) > 0: raise ValueError("Shift does not fit in long") else: ans = self._new_c(0) ans.ordp = 0 return ans
cdef pAdicZZpXCRElement _rshift_c(self, long n): """ Divides self by the uniformizer raised to the power ``n``. If parent is not a field, throws away the non-positive part of the series expansion. If ``n`` is negative, left shifts by ``-n``.
EXAMPLES::
sage: R = Zp(5,5,print_mode='digits') sage: S.<x> = R[] sage: f = x^5 + 75*x^3 - 15*x^2 +125*x - 5 sage: W.<w> = R.ext(f) sage: z = (1 + w)^5 sage: for m in range(26): repr(z >> m) # indirect doctest '...4001400444441030421100001' '...400140044444103042110000' '...40014004444410304211000' '...4001400444441030421100' '...400140044444103042110' '...40014004444410304211' '...4001400444441030421' '...400140044444103042' '...40014004444410304' '...4001400444441030' '...400140044444103' '...40014004444410' '...4001400444441' '...400140044444' '...40014004444' '...4001400444' '...400140044' '...40014004' '...4001400' '...400140' '...40014' '...4001' '...400' '...40' '...4' '...' sage: repr(z >> (-4)) '...40014004444410304211000010000' """ return self cdef long arelprec arelprec = -self.relprec else: cdef pAdicZZpXCRElement ans ZZ_pX_right_pshift(ans.unit, self.unit, self.prime_pow.pow_ZZ_tmp(n - self.ordp)[0], self.prime_pow.get_context(ans.relprec).x) else: else:
def __rshift__(pAdicZZpXCRElement self, shift): """ Divides self by the uniformizer raised to the power ``n``. If parent is not a field, throws away the non-positive part of the series expansion. If ``n`` is negative, left shifts by ``-n``.
EXAMPLES::
sage: R = Zp(5,5) sage: S.<x> = R[] sage: f = x^5 + 75*x^3 - 15*x^2 +125*x - 5 sage: W.<w> = R.ext(f) sage: z = (1 + w)^5 sage: z 1 + w^5 + w^6 + 2*w^7 + 4*w^8 + 3*w^10 + w^12 + 4*w^13 + 4*w^14 + 4*w^15 + 4*w^16 + 4*w^17 + 4*w^20 + w^21 + 4*w^24 + O(w^25) sage: z >> (6) # indirect doctest 1 + 2*w + 4*w^2 + 3*w^4 + w^6 + 4*w^7 + 4*w^8 + 4*w^9 + 4*w^10 + 4*w^11 + 4*w^14 + w^15 + 4*w^18 + O(w^19) sage: z >> (-4) w^4 + w^9 + w^10 + 2*w^11 + 4*w^12 + 3*w^14 + w^16 + 4*w^17 + 4*w^18 + 4*w^19 + 4*w^20 + 4*w^21 + 4*w^24 + w^25 + 4*w^28 + O(w^29) sage: F = W.fraction_field() sage: z = F(z) sage: z >> 7 w^-7 + w^-2 + w^-1 + 2 + 4*w + 3*w^3 + w^5 + 4*w^6 + 4*w^7 + 4*w^8 + 4*w^9 + 4*w^10 + 4*w^13 + w^14 + 4*w^17 + O(w^18) """ cdef pAdicZZpXCRElement ans if self._is_exact_zero(): return self if self.prime_pow.in_field or mpz_sgn((<Integer>shift).value) < 0: raise ValueError("valuation overflow") else: ans = self._new_c(0) ans.ordp = 0 return ans
cpdef _neg_(self): """ Returns ``-self``.
EXAMPLES::
sage: R = Zp(5,5) sage: S.<x> = R[] sage: f = x^5 + 75*x^3 - 15*x^2 +125*x - 5 sage: W.<w> = R.ext(f) sage: z = (1 + w)^5; z 1 + w^5 + w^6 + 2*w^7 + 4*w^8 + 3*w^10 + w^12 + 4*w^13 + 4*w^14 + 4*w^15 + 4*w^16 + 4*w^17 + 4*w^20 + w^21 + 4*w^24 + O(w^25) sage: -z # indirect doctest 4 + 3*w^5 + 4*w^6 + w^7 + w^8 + w^9 + w^10 + w^11 + 2*w^12 + 4*w^13 + 4*w^15 + 3*w^16 + w^17 + 2*w^18 + 3*w^19 + 2*w^21 + 4*w^23 + 4*w^24 + O(w^25) sage: y = z + (-z); y O(w^25) sage: -y O(w^25) sage: -W(0) 0 """
# / 1 + \alpha^p \pi_K^{p \lambda} mod \mathfrak{p}_K^{p \lambda + 1} if 1 \le \lambda < \frac{e_K}{p-1} # (1 + \alpha \pi^{\lambda})^p \equiv { 1 + (\alpha^p - \epsilon \alpha) \pi_K^{p \lambda} mod \mathfrak{p}_K^{p \lambda + 1} if \lambda = \frac{e_K}{p-1} # \ 1 - \epsilon \alpha \pi_K^{\lambda + e} mod \mathfrak{p}_K^{\lambda + e + 1} if \lambda > \frac{e_K}{p-1}
def __pow__(pAdicZZpXCRElement self, _right, m): # m ignored r""" Computes ``self^right``.
Note: when ``right`` is divisible by `p` then one can get more precision than expected.
Lemma 2.1 (Constructing Class Fields over Local Fields, Sebastian Pauli):
Let `\alpha` be in `\mathcal{O}_K`. Let
.. MATH::
p = -\pi_K^{e_K} \epsilon
be the factorization of `p` where `\epsilon` is a unit. Then the `p`-th power of `1 + \alpha \pi_K^{\lambda}` satisfies
.. MATH::
(1 + \alpha \pi^{\lambda})^p \equiv \left{ \begin{array}{lll} 1 + \alpha^p \pi_K^{p \lambda} & \mod \mathfrak{p}_K^{p \lambda + 1} & \mbox{if $1 \le \lambda < \frac{e_K}{p-1}$} \\ 1 + (\alpha^p - \epsilon \alpha) \pi_K^{p \lambda} & \mod \mathfrak{p}_K^{p \lambda + 1} & \mbox{if $\lambda = \frac{e_K}{p-1}$} \\ 1 - \epsilon \alpha \pi_K^{\lambda + e} & \mod \mathfrak{p}_K^{\lambda + e + 1} & \mbox{if $\lambda > \frac{e_K}{p-1}$} \end{array} \right.
So if ``right`` is divisible by `p^k` we can multiply the relative precision by `p` until we exceed `e/(p-1)`, then add `e` until we have done a total of `k` things: the precision of the result can therefore be greater than the precision of ``self``.
There is also the issue of `p`-adic exponents, and determining how the precision of the exponent affects the precision of the result.
In computing `(a + O(\pi^k))^{b + O(p^m)}`, one needs that the reduction of `a` mod `\pi` is in the prime field `\mathbb{F}_p` (so that the `p^m` power of the Teichmuller part is constant as `m` increases). Given this restriction, we can factor out the Teichmuller part and use the above lemma to find the first spot where
.. MATH::
(1 + \alpha \pi^{\lambda})^{p^m}
differs from 1. We compare this with the precision bound given by computing `(a + O(\pi^k))^b` and take the lesser of the two.
In order to do this we need to compute the valuation of ``(self / self.parent().teichmuller(self)) - 1``.
EXAMPLES::
sage: R = Zp(5,5) sage: S.<x> = R[] sage: f = x^5 + 75*x^3 - 15*x^2 +125*x - 5 sage: W.<w> = R.ext(f) sage: (1 + w)^5 # indirect doctest 1 + w^5 + w^6 + 2*w^7 + 4*w^8 + 3*w^10 + w^12 + 4*w^13 + 4*w^14 + 4*w^15 + 4*w^16 + 4*w^17 + 4*w^20 + w^21 + 4*w^24 + O(w^25) sage: (1 + w)^-5 1 + 4*w^5 + 4*w^6 + 3*w^7 + w^8 + 2*w^10 + w^11 + w^12 + 2*w^14 + 3*w^16 + 3*w^17 + 4*w^18 + 4*w^19 + 2*w^20 + 2*w^21 + 4*w^22 + 3*w^23 + 3*w^24 + O(w^25) sage: (1 + w + O(w^19))^5 1 + w^5 + w^6 + 2*w^7 + 4*w^8 + 3*w^10 + w^12 + 4*w^13 + 4*w^14 + 4*w^15 + 4*w^16 + 4*w^17 + 4*w^20 + w^21 + O(w^24) sage: (1 + O(w))^5 1 + O(w^5) sage: (1 + w + O(w^3))^25 1 + w^10 + w^11 + 4*w^12 + O(w^13) sage: (3 + 2*w + w^2 + O(w^6))^(15 + O(125)) 2 + 4*w^6 + w^7 + 3*w^8 + 3*w^9 + 4*w^10 + O(w^11) sage: (3 + 2*w + w^2 + O(w^6))^(15 + O(25)) 2 + 4*w^6 + w^7 + 3*w^8 + 3*w^9 + O(w^10) sage: (3 + w^2 + O(w^6))^(15+O(25)) 2 + w^5 + 4*w^7 + w^9 + 3*w^10 + O(w^11) sage: R = Zp(2, 10) sage: S.<x> = R[] sage: f = x^34 + 18*x^5 - 72*x^3 + 2 sage: W.<w> = R.ext(f) sage: (1+w+O(w^2))^8 1 + w^8 + O(w^16) sage: (1+w+O(w^2))^16 1 + w^16 + O(w^32) sage: (1+w+O(w^2))^32 1 + w^32 + w^50 + w^55 + w^60 + O(w^64) sage: (1+w+O(w^2))^64 1 + w^64 + w^66 + w^71 + w^76 + w^81 + w^84 + w^86 + w^91 + w^94 + w^96 + O(w^98)
TESTS:
We define ``0^0`` to be unity, :trac:`13786`::
sage: R = Zp(5,5) sage: S.<x> = R[] sage: f = x^5 + 75*x^3 - 15*x^2 +125*x - 5 sage: W.<w> = R.ext(f) sage: type(W(0)) <type 'sage.rings.padics.padic_ZZ_pX_CR_element.pAdicZZpXCRElement'> sage: W(0)^0 1 + O(w^25) sage: W(0)^0 == W(1) True
The value returned from ``0^0`` should belong to our ring::
sage: R = Zp(5,5) sage: S.<x> = R[] sage: f = x^5 + 75*x^3 - 15*x^2 +125*x - 5 sage: W.<w> = R.ext(f) sage: type(W(0)^0) == type(W(0)) True
""" cdef Integer right cdef bint padic_exp cdef long exp_prec cdef long exp_val cdef long relprec cdef long threshold # e / (p-1) cdef long prime_long cdef mpz_t tmp, tmp2 threshold = 0 else: cdef Integer base_level cdef pAdicZZpXCRElement ans cdef long i # Return 0 except for 0^0 error or type error on the exponent. else: raise TypeError("exponent must be an integer, rational or base p-adic with the same prime") # If an integer exponent, return an inexact zero of valuation right * self.ordp. Otherwise raise an error. _right = Integer(_right) raise ValueError("valuation overflow") elif isinstance(_right, Rational) or (isinstance(_right, pAdicGenericElement) and _right._is_base_elt(self.prime_pow.prime)): raise ValueError("Need more precision") else: raise TypeError("exponent must be an integer, rational or base p-adic with the same prime") # return 1 to maximum precision raise ValueError("in order to raise to a p-adic exponent, base must be a unit") raise NotImplementedError("negative valuation exponents not yet supported") # checks to see if the residue of self.unit is in the prime field. for i from 1 <= i <= ZZ_pX_deg(self.unit): if not ZZ_divide_test(ZZ_p_rep(ZZ_pX_coeff(self.unit, i)), self.prime_pow.pow_ZZ_tmp(1)[0]): raise ValueError("in order to raise to a p-adic exponent, base must reduce to an element of F_p mod the uniformizer") # compute the "level" elif isinstance(_right, Rational): raise NotImplementedError else: raise TypeError("exponent must be an integer, rational or base p-adic with the same prime") # Now we compute the increased relprec due to the exponent having positive p-adic valuation else: else: # Now we compute the limit on relprec due to a non-infinite precision on the exponent. # I can freely change base_level, so I use it in place of tmp above. else: ans = self._new_c(0) ans.ordp = 0 return ans else: raise ValueError("valuation overflow") ZZ_pX_InvMod_newton_unram(ans.unit, self.unit, self.prime_pow.get_modulus(ans.relprec)[0], self.prime_pow.get_context(ans.relprec).x, self.prime_pow.get_context(1).x) else: else:
cpdef _add_(self, _right): """ Computes the sum of ``self`` and ``right``.
EXAMPLES::
sage: R = Zp(5,5) sage: S.<x> = R[] sage: f = x^5 + 75*x^3 - 15*x^2 +125*x - 5 sage: W.<w> = R.ext(f) sage: (4*w^5 + 3*w^7 + w^9 + 2*w^10 + 2*w^11 + O(w^13)) - 69 # indirect doctest 1 + O(w^13) sage: -69 + (4*w^5 + 3*w^7 + w^9 + 2*w^10 + 2*w^11 + O(w^13)) 1 + O(w^13) sage: y = (4*w^5 + 3*w^7 + w^9 + 2*w^10 + 2*w^11 + O(w^13)) sage: y - 70 O(w^13) sage: y + 0 4*w^5 + 3*w^7 + w^9 + 2*w^10 + 2*w^11 + O(w^13) """ cdef pAdicZZpXCRElement ans cdef long tmpL cdef ZZ_pX_c tmpP else: ans.relprec = -ans.relprec ans = self._new_c(0) ans.ordp = right.ordp else: ans.relprec = -ans.relprec # The relative precision of the sum is the minimum of the relative precisions in this case, possibly decreasing if we got cancellation # Since the valuations are the same, we could just add the units, if they had the same modulus. # But they don't necessarily, so we may have to conv_modulus # conv_modulus should have restored the context, so we don't need to again. else: # conv_modulus should have restored the context, so we don't need to again. else: else: # if self is normalized, then the valuations are actually different so the sum will be normalized. else: else: else: # if right is normalized, then the valuations are actually different so the sum will be normalized.
cpdef _sub_(self, right): """ Returns the difference of ``self`` and ``right``.
EXAMPLES::
sage: R = Zp(5,5) sage: S.<x> = R[] sage: f = x^5 + 75*x^3 - 15*x^2 +125*x - 5 sage: W.<w> = R.ext(f) sage: a = W(329) sage: b = W(111) sage: a - b #indirect doctest 3 + 3*w^5 + w^7 + 2*w^9 + 3*w^10 + 4*w^11 + 2*w^13 + 2*w^14 + w^15 + 4*w^16 + 2*w^18 + 3*w^19 + 2*w^20 + 3*w^21 + w^22 + w^24 + O(w^25) sage: W(218) 3 + 3*w^5 + w^7 + 2*w^9 + 3*w^10 + 4*w^11 + 2*w^13 + 2*w^14 + w^15 + 4*w^16 + 2*w^18 + 3*w^19 + 2*w^20 + 3*w^21 + w^22 + w^24 + O(w^25) sage: a - O(w^14) 4 + 3*w^10 + 2*w^12 + O(w^14) sage: a - 0 4 + 3*w^10 + 2*w^12 + w^14 + 2*w^15 + w^16 + 3*w^17 + 3*w^18 + w^19 + 2*w^21 + 4*w^22 + w^23 + 4*w^24 + O(w^25) sage: O(w^14) - a 1 + 4*w^5 + 3*w^7 + w^9 + w^10 + 2*w^11 + w^12 + w^13 + O(w^14) """ # For now, a simple implementation
cpdef _mul_(self, _right): """ Returns the product of ``self`` and ``right``.
EXAMPLES::
sage: R = Zp(5,5) sage: S.<x> = R[] sage: f = x^5 + 75*x^3 - 15*x^2 +125*x - 5 sage: W.<w> = R.ext(f) sage: a = W(329) sage: b = W(111) sage: a*b #indirect doctest 4 + 3*w^5 + w^7 + 2*w^9 + 4*w^11 + 3*w^12 + 2*w^13 + w^14 + 2*w^15 + 3*w^16 + 4*w^17 + 4*w^18 + 2*w^19 + 2*w^21 + 4*w^22 + 2*w^23 + w^24 + O(w^25) sage: a * 0 0 sage: a * O(w^14) O(w^14) """ cdef ZZ_pX_c modulus_corrected cdef ntl_ZZ_pContext_class ctx cdef pAdicZZpXCRElement ans else: else:
cpdef _div_(self, right): """ Returns the quotient of ``self`` by ``right``.
EXAMPLES::
sage: R = Zp(5,5) sage: S.<x> = R[] sage: f = x^5 + 75*x^3 - 15*x^2 +125*x - 5 sage: W.<w> = R.ext(f) sage: W(14) / W(125) #indirect doctest 4*w^-15 + w^-13 + 3*w^-11 + 2*w^-10 + 3*w^-9 + 4*w^-8 + 4*w^-7 + 3*w^-6 + 2*w^-5 + 4*w^-4 + 3*w^-3 + 2*w^-2 + 4*w^-1 + 2 + w^2 + w^4 + 4*w^5 + w^6 + w^7 + 3*w^9 + O(w^10) sage: 1 / w w^-1 + O(w^24) sage: W.<w> = R.ext(x^25 - 165*x + 5) sage: a = (1 + w)^25 - 1 sage: b = (1 + w)^5 - 1 sage: c = (1 + w)^20 + (1 + w)^15 + (1 + w)^10 + (1 + w)^5 + 1 sage: d = a / b; d == c True sage: d.precision_absolute() 120 sage: c.precision_absolute() 125 sage: 1 / a == ~a True """ # for now, a simple implementation
def __copy__(self): """ Returns a copy of ``self``.
EXAMPLES::
sage: R = Zp(5,5) sage: S.<x> = R[] sage: f = x^5 + 75*x^3 - 15*x^2 +125*x - 5 sage: W.<w> = R.ext(f) sage: b = W(45, 17); b 4*w^5 + 3*w^7 + w^9 + w^10 + 2*w^11 + w^12 + w^13 + 3*w^14 + w^16 + O(w^17) sage: c = copy(b); c 4*w^5 + 3*w^7 + w^9 + w^10 + 2*w^11 + w^12 + w^13 + 3*w^14 + w^16 + O(w^17) sage: c is b False """
def _integer_(self, Z=None): """ Returns an integer congruent to this element modulo `\pi`^``self.absolute_precision()``, if possible.
EXAMPLES::
sage: ZZ(ZqCR(125,names='a')(-1)) #indirect doctest 95367431640624 sage: R = Zp(5); S.<x> = ZZ[]; f = x^5 + 25*x^3 - 5; W.<w> = R.ext(f) sage: ZZ(W(-1)) 95367431640624 sage: ZZ(W(0)) 0 sage: ZZ(W(0,7)) 0 sage: ZZ(w) Traceback (most recent call last): ... ValueError: This element not well approximated by an integer. sage: ZZ(W(5)) # todo: this should be different... 381469726562505 """ cdef Integer ans cdef ZZ_c tmp_z self._normalize() if self.ordp < 0: raise ValueError("This element has negative valuation")
def is_zero(self, absprec = None): """ Returns whether the valuation of ``self`` is at least ``absprec``. If ``absprec`` is ``None``, returns if ``self`` is indistinguishable from zero.
If ``self`` is an inexact zero of valuation less than ``absprec``, raises a PrecisionError.
EXAMPLES::
sage: R = Zp(5,5) sage: S.<x> = R[] sage: f = x^5 + 75*x^3 - 15*x^2 +125*x - 5 sage: W.<w> = R.ext(f) sage: O(w^189).is_zero() True sage: W(0).is_zero() True sage: a = W(675) sage: a.is_zero() False sage: a.is_zero(7) True sage: a.is_zero(21) False """ cdef bint ans cdef long aprec else: absprec = Integer(absprec) if mpz_sgn((<Integer>absprec).value) < 0: ans = True elif self.relprec == 0: raise PrecisionError("Not enough precision to determine if element is zero") else: ans = False else: raise PrecisionError("Not enough precision to determine if element is zero") else:
cpdef ntl_ZZ_pX _ntl_rep_unnormalized(self): """ Returns an ``ntl_ZZ_pX`` holding the current unit part of ``self``.
``self`` is not normalized before this, so the polynomial returned may not actually be a unit.
EXAMPLES::
sage: R = Zp(5,5) sage: S.<x> = R[] sage: f = x^5 + 75*x^3 - 15*x^2 +125*x - 5 sage: W.<w> = R.ext(f) sage: a = W(566); b = W(209) sage: c = a + b; c._ntl_rep_unnormalized() [775] sage: c w^10 + 4*w^12 + 2*w^14 + w^15 + 2*w^16 + 4*w^17 + w^18 + w^20 + 2*w^21 + 3*w^22 + w^23 + w^24 + O(w^25) sage: c._ntl_rep_unnormalized() [106 60 114 35 112] """ raise ValueError("self == 0")
cpdef ntl_ZZ_pX _ntl_rep(self): """ Returns an ``ntl_ZZ_pX`` that holds the unit part of ``self``.
EXAMPLES::
sage: R = Zp(5,5) sage: S.<x> = R[] sage: f = x^5 + 75*x^3 - 15*x^2 +125*x - 5 sage: W.<w> = R.ext(f) sage: a = W(566); b = W(209) sage: c = a + b; c._ntl_rep() [106 60 114 35 112] sage: c w^10 + 4*w^12 + 2*w^14 + w^15 + 2*w^16 + 4*w^17 + w^18 + w^20 + 2*w^21 + 3*w^22 + w^23 + w^24 + O(w^25) sage: c._ntl_rep() [106 60 114 35 112] """
cpdef _ntl_rep_abs(self): """ Returns a pair ``(f, k)`` where ``f`` is an ``ntl_ZZ_pX`` and ``k`` is a non-positive integer such that ``self = f(self.parent.gen())*p^k``
EXAMPLES::
sage: R = Zp(5,5) sage: S.<x> = R[] sage: f = x^5 + 75*x^3 - 15*x^2 +125*x - 5 sage: W.<w> = R.ext(f) sage: a = W(566); b = W(209) sage: c = a + b; c._ntl_rep_abs() ([775], 0) sage: c w^10 + 4*w^12 + 2*w^14 + w^15 + 2*w^16 + 4*w^17 + w^18 + w^20 + 2*w^21 + 3*w^22 + w^23 + w^24 + O(w^25) sage: c._ntl_rep_abs() ([775], 0) sage: (~c)._ntl_rep_abs() ([121], -2) sage: ~c w^-10 + w^-8 + 4*w^-6 + 4*w^-5 + 3*w^-3 + 4*w^-2 + 3*w^-1 + 4 + 4*w + 2*w^2 + 4*w^3 + 3*w^4 + O(w^5) sage: ~c * 25 1 + 4*w^5 + 3*w^7 + w^9 + 4*w^10 + 2*w^11 + 3*w^12 + w^13 + 4*w^14 + O(w^15) sage: W(121) 1 + 4*w^5 + 3*w^7 + w^9 + 4*w^10 + 2*w^11 + 3*w^12 + w^13 + 4*w^14 + 2*w^16 + 3*w^17 + 3*w^18 + 4*w^19 + 4*w^20 + 3*w^21 + w^22 + w^23 + 4*w^24 + O(w^25) """ cdef ntl_ZZ_pContext_class ctx cdef long little_shift, ppow else: little_shift = self.prime_pow.e - little_shift else: # self = x^(self.prime_pow.e * ppow) * x^(little_shift) * self.unit # so we want to _internal_lshift dummy.unit by little_shift # and then write # self = p^(ppow) * (x^e/p)^(ppow) * dummy.unit # so we need to multiply dummy.unit by (p/x^e)^(-ppow) in the Eisenstein case # which we can do by _pshift_self
def polynomial(self, var='x'): """ Returns a polynomial over the base ring that yields this element when evaluated at the generator of the parent.
INPUT:
- ``var`` -- string, the variable name for the polynomial
EXAMPLES::
sage: S.<x> = ZZ[] sage: W.<w> = Zp(5).extension(x^2 - 5) sage: (w + W(5, 7)).polynomial() (1 + O(5^3))*x + (5 + O(5^4)) """ L = [R(c, prec) >> k for c in L] else:
cdef ZZ_p_c _const_term(self): """ Returns the constant term of ``self.unit``.
Note: this may be divisible by `p` if ``self`` is not normalized.
EXAMPLES::
sage: R = Zp(5,5) sage: S.<x> = R[] sage: f = x^5 + 75*x^3 - 15*x^2 +125*x - 5 sage: W.<w> = R.ext(f) sage: a = W(566) sage: a._const_term_test() #indirect doctest 566 """
def is_equal_to(self, right, absprec = None): """ Returns whether ``self`` is equal to ``right`` modulo ``self.uniformizer()^absprec``.
If ``absprec`` is ``None``, returns if ``self`` is equal to ``right`` modulo the lower of their two precisions.
EXAMPLES::
sage: R = Zp(5,5) sage: S.<x> = R[] sage: f = x^5 + 75*x^3 - 15*x^2 +125*x - 5 sage: W.<w> = R.ext(f) sage: a = W(47); b = W(47 + 25) sage: a.is_equal_to(b) False sage: a.is_equal_to(b, 7) True """ # Should be sped up later
# def lift(self): # """ # Returns an element of a number field defined by the same polynomial as self's parent that is congruent to self modulo an appropriate ideal.
# Not currently implemented. # """ # raise NotImplementedError
cpdef pAdicZZpXCRElement lift_to_precision(self, absprec=None): """ Returns a ``pAdicZZpXCRElement`` congruent to ``self`` but with absolute precision at least ``absprec``.
INPUT:
- ``absprec`` -- (default ``None``) the absolute precision of the result. If ``None``, lifts to the maximum precision allowed.
.. NOTE::
If setting ``absprec`` that high would violate the precision cap, raises a precision error. If self is an inexact zero and ``absprec`` is greater than the maximum allowed valuation, raises an error.
Note that the new digits will not necessarily be zero.
EXAMPLES::
sage: R = Zp(5,5) sage: S.<x> = R[] sage: f = x^5 + 75*x^3 - 15*x^2 +125*x - 5 sage: W.<w> = R.ext(f) sage: a = W(345, 17); a 4*w^5 + 3*w^7 + w^9 + 3*w^10 + 2*w^11 + 4*w^12 + w^13 + 2*w^14 + 2*w^15 + O(w^17) sage: b = a.lift_to_precision(19); b 4*w^5 + 3*w^7 + w^9 + 3*w^10 + 2*w^11 + 4*w^12 + w^13 + 2*w^14 + 2*w^15 + w^17 + 2*w^18 + O(w^19) sage: c = a.lift_to_precision(24); c 4*w^5 + 3*w^7 + w^9 + 3*w^10 + 2*w^11 + 4*w^12 + w^13 + 2*w^14 + 2*w^15 + w^17 + 2*w^18 + 4*w^19 + 4*w^20 + 2*w^21 + 4*w^23 + O(w^24) sage: a._ntl_rep() [19 35 118 60 121] sage: b._ntl_rep() [19 35 118 60 121] sage: c._ntl_rep() [19 35 118 60 121] sage: a.lift_to_precision().precision_relative() == W.precision_cap() True """ cdef pAdicZZpXCRElement ans cdef long aprec, rprec return self absprec = Integer(absprec) # return an exact zero ans = self._new_c(0) ans._set_exact_zero() return ans if mpz_sgn((<Integer>absprec).value) < 0 or self.relprec == self.prime_pow.ram_prec_cap: return self else: if self.relprec == 0: raise ValueError("absprec larger than maximum allowable valuation") else: raise PrecisionError("Precision higher than allowed by the precision cap.") else: return self raise ValueError("absprec larger than maximum allowable valuation") else: # Now we're done handling all the special cases. raise PrecisionError("Precision higher than allowed by the precision cap.")
def expansion(self, n = None, lift_mode = 'simple'): """ Returns a list giving a series representation of self.
- If ``lift_mode == 'simple'`` or ``'smallest'``, the returned list will consist of integers (in the Eisenstein case) or a list of lists of integers (in the unramified case). ``self`` can be reconstructed as a sum of elements of the list times powers of the uniformiser (in the Eisenstein case), or as a sum of powers of the `p` times polynomials in the generator (in the unramified case).
+ If ``lift_mode == 'simple'``, all integers will be in the interval `[0,p-1]`.
+ If ``lift_mode == 'smallest'`` they will be in the interval `[(1-p)/2, p/2]`.
- If ``lift_mode == 'teichmuller'``, returns a list of ``pAdicZZpXCRElements``, all of which are Teichmuller representatives and such that ``self`` is the sum of that list times powers of the uniformizer.
Note that zeros are truncated from the returned list if ``self.parent()`` is a field, so you must use the ``valuation`` function to fully reconstruct ``self``.
INPUT:
- ``n`` -- integer (default ``None``). If given, returns the corresponding entry in the expansion.
EXAMPLES::
sage: R = Zp(5,5) sage: S.<x> = R[] sage: f = x^5 + 75*x^3 - 15*x^2 +125*x - 5 sage: W.<w> = R.ext(f) sage: y = W(775, 19); y w^10 + 4*w^12 + 2*w^14 + w^15 + 2*w^16 + 4*w^17 + w^18 + O(w^19) sage: (y>>9).expansion() [0, 1, 0, 4, 0, 2, 1, 2, 4, 1] sage: (y>>9).expansion(lift_mode='smallest') [0, 1, 0, -1, 0, 2, 1, 2, 0, 1] sage: w^10 - w^12 + 2*w^14 + w^15 + 2*w^16 + w^18 + O(w^19) w^10 + 4*w^12 + 2*w^14 + w^15 + 2*w^16 + 4*w^17 + w^18 + O(w^19) sage: g = x^3 + 3*x + 3 sage: A.<a> = R.ext(g) sage: y = 75 + 45*a + 1200*a^2; y 4*a*5 + (3*a^2 + a + 3)*5^2 + 4*a^2*5^3 + a^2*5^4 + O(5^6) sage: E = y.expansion(); E 5-adic expansion of 4*a*5 + (3*a^2 + a + 3)*5^2 + 4*a^2*5^3 + a^2*5^4 + O(5^6) sage: list(E) [[], [0, 4], [3, 1, 3], [0, 0, 4], [0, 0, 1], []] sage: list(y.expansion(lift_mode='smallest')) [[], [0, -1], [-2, 2, -2], [1], [0, 0, 2], []] sage: 5*((-2*5 + 25) + (-1 + 2*5)*a + (-2*5 + 2*125)*a^2) 4*a*5 + (3*a^2 + a + 3)*5^2 + 4*a^2*5^3 + a^2*5^4 + O(5^6) sage: list(W(0).expansion()) [] sage: list(W(0,4).expansion()) [] sage: list(A(0,4).expansion()) [] """ zero = self.parent()(0) zero = [] else: deprecation(14825, "Interface to expansion has changed; first argument now n") lift_mode = n n = None return self.slice(n.start, n.stop, n.step) raise PrecisionError cdef Integer ordp elif lift_mode == 'teichmuller': if n is None: ulist = self.teichmuller_expansion() else: return self.teichmuller_expansion(n) else: raise ValueError("lift mode must be one of 'simple', 'smallest' or 'teichmuller'") except IndexError: return zero
list = deprecated_function_alias(14825, expansion)
def matrix_mod_pn(self): """ 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^{N / e}` where `N` is the absolute precision of this element (unless this element is zero to arbitrary precision; in that case the entries are integer zeros.)
Raises an error if this element has negative valuation.
EXAMPLES::
sage: R = ZpCR(5,5) sage: S.<x> = R[] sage: f = x^5 + 75*x^3 - 15*x^2 +125*x - 5 sage: W.<w> = R.ext(f) sage: a = (3+w)^7 sage: a.matrix_mod_pn() [2757 333 1068 725 2510] [ 50 1507 483 318 725] [ 500 50 3007 2358 318] [1590 1375 1695 1032 2358] [2415 590 2370 2970 1032]
TESTS:
Check that :trac:`13617` has been fixed::
sage: W.zero().matrix_mod_pn() [0 0 0 0 0] [0 0 0 0 0] [0 0 0 0 0] [0 0 0 0 0] [0 0 0 0 0]
""" raise ValueError("self must be integral") cdef ZZ_pX_c x cdef Py_ssize_t i, j
# def matrix(self, base = None): # """ # If base is None, return 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 \emph{rows} of this matrix # give the images of each of the `x^i`.
# If base is not None, then base must be either a field that # embeds in the parent of self or a morphism to the parent of # self, in which case this function returns the matrix of # multiplication by self on the power basis, where we view the # parent field as a field over base.
# INPUT: # base -- field or morphism # """ # raise NotImplementedError
# def multiplicative_order(self, prec=None): # """ # Returns the multiplicative order of self, ie the smallest # positive n so that there is an exact p-adic element congruent # to self modulo self's precision that is an nth root of unity.
# Note: unlike the case for Qp and Zp, it is possible to have # non-teichmuller elements with finite orders. This can happen # only if (p-1) divides the ramification index (see the # documentation on __pow__).
# INPUT:
# - self -- a p-adic element # - prec -- an integer
# OUTPUT:
# - integer -- the multiplicative order of self # """ # raise NotImplementedError
def teichmuller_expansion(self, n = None): r""" Returns a list [`a_0`, `a_1`,..., `a_n`] such that
- `a_i^q = a_i` - ``self.unit_part()`` = `\sum_{i = 0}^n a_i \pi^i`, where `\pi` is a uniformizer of ``self.parent()`` - if `a_i \ne 0`, the absolute precision of `a_i` is ``self.precision_relative() - i``
INPUT:
- ``n`` -- integer (default ``None``). If given, returns the corresponding entry in the expansion.
EXAMPLES::
sage: R.<a> = ZqCR(5^4,4) sage: E = a.teichmuller_expansion(); E 5-adic expansion of a + O(5^4) (teichmuller) sage: list(E) [a + (2*a^3 + 2*a^2 + 3*a + 4)*5 + (4*a^3 + 3*a^2 + 3*a + 2)*5^2 + (4*a^2 + 2*a + 2)*5^3 + O(5^4), (3*a^3 + 3*a^2 + 2*a + 1) + (a^3 + 4*a^2 + 1)*5 + (a^2 + 4*a + 4)*5^2 + O(5^3), (4*a^3 + 2*a^2 + a + 1) + (2*a^3 + 2*a^2 + 2*a + 4)*5 + O(5^2), (a^3 + a^2 + a + 4) + O(5)] sage: sum([c * 5^i for i, c in enumerate(E)]) a + O(5^4) sage: all([c^625 == c for c in E]) True
sage: S.<x> = ZZ[] sage: f = x^3 - 98*x + 7 sage: W.<w> = ZpCR(7,3).ext(f) sage: b = (1+w)^5; L = b.teichmuller_expansion(); L [1 + O(w^9), 5 + 5*w^3 + w^6 + 4*w^7 + O(w^8), 3 + 3*w^3 + O(w^7), 3 + 3*w^3 + O(w^6), O(w^5), 4 + 5*w^3 + O(w^4), 3 + O(w^3), 6 + O(w^2), 6 + O(w)] sage: sum([w^i*L[i] for i in range(9)]) == b True sage: all([L[i]^(7^3) == L[i] for i in range(9)]) True
sage: L = W(3).teichmuller_expansion(); L [3 + 3*w^3 + w^7 + O(w^9), O(w^8), O(w^7), 4 + 5*w^3 + O(w^6), O(w^5), O(w^4), 3 + O(w^3), 6 + O(w^2)] sage: sum([w^i*L[i] for i in range(len(L))]) 3 + O(w^9) """ cdef pAdicZZpXCRElement v return L elif self._is_exact_zero() or n < self.ordp: return self.parent()(0) elif n >= self.ordp + rp: raise PrecisionError else: v = self._new_c(rp) cdef long goal elif rp == goal: return v elif rp == goal: v = self._new_c(0) v._set_inexact_zero(rp) return v else: v = self._new_c(0) v._set_inexact_zero(rp) return v
teichmuller_list = deprecated_function_alias(14825, teichmuller_expansion)
def _teichmuller_set_unsafe(self): """ Sets this element to the Teichmuller representative with the same residue.
.. WARNING::
This function modifies the element, which is not safe. Elements are supposed to be immutable.
EXAMPLES::
sage: R = Zp(7,5) sage: S.<x> = R[] sage: f = x^5 + 77*x^3 - 98*x^2 - 7 sage: W.<w> = R.ext(f) sage: y = W.teichmuller(3, 15); y #indirect doctest 3 + 4*w^5 + 2*w^8 + 6*w^10 + w^11 + 6*w^12 + 5*w^13 + 4*w^14 + O(w^15)
sage: y^7 == y True sage: g = x^3 + 3*x^2 + 4 sage: A.<a> = R.ext(g) sage: b = A.teichmuller(1 + 2*a - a^2); b (6*a^2 + 2*a + 1) + (5*a + 3)*7 + (5*a + 5)*7^2 + (4*a^2 + 4*a + 2)*7^3 + (2*a + 1)*7^4 + O(7^5) sage: b^343 == b True
TESTS:
We check that :trac:`8239` is resolved::
sage: K.<a> = Qq(25) sage: K.teichmuller(K(2/5)) Traceback (most recent call last): ... ValueError: cannot set negative valuation element to Teichmuller representative. """ self._set_exact_zero() raise ValueError("cannot set negative valuation element to Teichmuller representative.") raise ValueError("not enough precision known") else:
# def padded_list(self, n, lift_mode = 'simple'): # """ # Returns a list of coefficients of pi starting with `pi^0` up to # `pi^n` exclusive (padded with zeros if needed)
# """ # raise NotImplementedError
def precision_absolute(self): """ Returns the absolute precision of ``self``, ie the power of the uniformizer modulo which this element is defined.
EXAMPLES::
sage: R = Zp(5,5) sage: S.<x> = R[] sage: f = x^5 + 75*x^3 - 15*x^2 +125*x - 5 sage: W.<w> = R.ext(f) sage: a = W(75, 19); a 3*w^10 + 2*w^12 + w^14 + w^16 + w^17 + 3*w^18 + O(w^19) sage: a.valuation() 10 sage: a.precision_absolute() 19 sage: a.precision_relative() 9 sage: a.unit_part() 3 + 2*w^2 + w^4 + w^6 + w^7 + 3*w^8 + O(w^9) sage: (a.unit_part() - 3).precision_absolute() 9 """ cdef Integer ans else: else:
def precision_relative(self): """ Returns the relative precision of ``self``, ie the power of the uniformizer modulo which the unit part of ``self`` is defined.
EXAMPLES::
sage: R = Zp(5,5) sage: S.<x> = R[] sage: f = x^5 + 75*x^3 - 15*x^2 +125*x - 5 sage: W.<w> = R.ext(f) sage: a = W(75, 19); a 3*w^10 + 2*w^12 + w^14 + w^16 + w^17 + 3*w^18 + O(w^19) sage: a.valuation() 10 sage: a.precision_absolute() 19 sage: a.precision_relative() 9 sage: a.unit_part() 3 + 2*w^2 + w^4 + w^6 + w^7 + 3*w^8 + O(w^9) """
# def residue(self, n = 1): # """ # Reduces this element modulo pi^n. # """ # raise NotImplementedError
cdef long valuation_c(self): """ Returns the valuation of ``self``.
EXAMPLES::
sage: R = Zp(5,5) sage: S.<x> = R[] sage: f = x^5 + 75*x^3 - 15*x^2 +125*x - 5 sage: W.<w> = R.ext(f) sage: a = W(75, 19); a 3*w^10 + 2*w^12 + w^14 + w^16 + w^17 + 3*w^18 + O(w^19) sage: a.valuation() # indirect doctest 10 sage: a.precision_absolute() 19 sage: a.precision_relative() 9 sage: a.unit_part() 3 + 2*w^2 + w^4 + w^6 + w^7 + 3*w^8 + O(w^9) """
cpdef pAdicZZpXCRElement unit_part(self): """ Returns the unit part of ``self``, ie ``self / uniformizer^(self.valuation())``
EXAMPLES::
sage: R = Zp(5,5) sage: S.<x> = R[] sage: f = x^5 + 75*x^3 - 15*x^2 +125*x - 5 sage: W.<w> = R.ext(f) sage: a = W(75, 19); a 3*w^10 + 2*w^12 + w^14 + w^16 + w^17 + 3*w^18 + O(w^19) sage: a.valuation() 10 sage: a.precision_absolute() 19 sage: a.precision_relative() 9 sage: a.unit_part() 3 + 2*w^2 + w^4 + w^6 + w^7 + 3*w^8 + O(w^9)
TESTS:
We check that :trac:`13616` is resolved::
sage: z = (1+w)^5 sage: y = z - 1 sage: t=y-y sage: t.unit_part() O(w^0) """
cdef ext_p_list(self, bint pos): """ Returns a list of integers (in the Eisenstein case) or a list of lists of integers (in the unramified case). ``self`` can be reconstructed as a sum of elements of the list times powers of the uniformiser (in the Eisenstein case), or as a sum of powers of `p` times polynomials in the generator (in the unramified case).
If ``pos`` is ``True``, all integers will be in the interval `[0,p-1]`, otherwise they will be in the interval `[(1-p)/2, p/2]`.
Note that zeros are truncated from the returned list, so you must use the ``valuation()`` function to completely recover ``self``.
EXAMPLES::
sage: R = Zp(5,5) sage: S.<x> = R[] sage: f = x^5 + 75*x^3 - 15*x^2 +125*x - 5 sage: W.<w> = R.ext(f) sage: y = W(775, 19); y w^10 + 4*w^12 + 2*w^14 + w^15 + 2*w^16 + 4*w^17 + w^18 + O(w^19) sage: y._ext_p_list(True) [1, 0, 4, 0, 2, 1, 2, 4, 1] sage: y._ext_p_list(False) [1, 0, -1, 0, 2, 1, 2, 0, 1] sage: w^10 - w^12 + 2*w^14 + w^15 + 2*w^16 + w^18 + O(w^19) w^10 + 4*w^12 + 2*w^14 + w^15 + 2*w^16 + 4*w^17 + w^18 + O(w^19) sage: g = x^3 + 3*x + 3 sage: A.<a> = R.ext(g) sage: y = 75 + 45*a + 1200*a^2; y 4*a*5 + (3*a^2 + a + 3)*5^2 + 4*a^2*5^3 + a^2*5^4 + O(5^6) sage: y._ext_p_list(True) [[0, 4], [3, 1, 3], [0, 0, 4], [0, 0, 1]] sage: y._ext_p_list(False) [[0, -1], [-2, 2, -2], [1], [0, 0, 2]] sage: 5*((-2*5 + 25) + (-1 + 2*5)*a + (-2*5 + 2*125)*a^2) 4*a*5 + (3*a^2 + a + 3)*5^2 + 4*a^2*5^3 + a^2*5^4 + O(5^6) """
def make_ZZpXCRElement(parent, unit, ordp, relprec, version): """ Unpickling.
EXAMPLES::
sage: R = Zp(5,5) sage: S.<x> = R[] sage: f = x^5 + 75*x^3 - 15*x^2 +125*x - 5 sage: W.<w> = R.ext(f) sage: y = W(775, 19); y w^10 + 4*w^12 + 2*w^14 + w^15 + 2*w^16 + 4*w^17 + w^18 + O(w^19) sage: loads(dumps(y)) #indirect doctest w^10 + 4*w^12 + 2*w^14 + w^15 + 2*w^16 + 4*w^17 + w^18 + O(w^19)
sage: from sage.rings.padics.padic_ZZ_pX_CR_element import make_ZZpXCRElement sage: make_ZZpXCRElement(W, y._ntl_rep(), 3, 9, 0) w^3 + 4*w^5 + 2*w^7 + w^8 + 2*w^9 + 4*w^10 + w^11 + O(w^12) """ cdef pAdicZZpXCRElement ans cdef ZZ_pX_c poly ans._set_inexact_zero(mpz_get_si((<Integer>ordp).value)) else: else: raise ValueError("unknown unpickling version") |