The classes in this file are designed to be attached to p-adic parents and elements for Cython access to properties of the parent.
In addition to storing the defining polynomial (as an NTL polynomial) at different precisions, they also cache powers of p and data to speed right shifting of elements.
The hierarchy of PowComputers splits first at whether it’s for a base ring (Qp or Zp) or an extension.
Among the extension classes (those in this file), they are first split by the type of NTL polynomial (ntl_ZZ_pX or ntl_ZZ_pEX), then by the amount and style of caching (see below). Finally, there are subclasses of the ntl_ZZ_pX PowComputers that cache additional information for Eisenstein extensions.
There are three styles of caching:
- FM: caches powers of p up to the cache_limit, only caches the polynomial modulus and the ntl_ZZ_pContext of precision prec_cap.
- small: Requires cache_limit = prec_cap. Caches p^k for every k up to the cache_limit and caches a polynomial modulus and a ntl_ZZ_pContext for each such power of p.
- big: Caches as the small does up to cache_limit and caches prec_cap. Also has a dictionary that caches values above the cache_limit when they are computed (rather than at ring creation time).
AUTHORS:
If n >= 0 returns ceil(n / self.e)
If n < 0 returns ceil(-n / self.e)
EXAMPLES:
sage: PC = PowComputer_ext_maker(5, 3, 10, 20, False, ntl.ZZ_pX([-5,0,1],5^10), 'FM', 'e',ntl.ZZ_pX([1],5^10))
sage: PC._capdiv_test(15)
8
sage: PC._capdiv_test(-7)
4
Returns a ZZ_pContext for self.prime^((n-1) // self.e + 1)
For Eisenstein extensions this gives the context used for an element of relative precision n.
EXAMPLES:
sage: PC = PowComputer_ext_maker(5, 10, 10, 20, False, ntl.ZZ_pX([-5, 0, 1], 5^10), 'FM', 'e',ntl.ZZ_pX([1],5^10))
sage: PC._get_context_capdiv_test(29)
NTL modulus 30517578125
Returns a ZZ_pContext for self.prime^n.
EXAMPLES:
sage: PC = PowComputer_ext_maker(5, 10, 10, 20, False, ntl.ZZ_pX([-5, 0, 1], 5^10), 'FM', 'e',ntl.ZZ_pX([1],5^10))
sage: PC._get_context_test(15)
NTL modulus 30517578125
Multiplies a and b modulo the modulus corresponding to self.polynomial() (mod self.prime^n).
EXAMPLES:
sage: A = PowComputer_ext_maker(5, 10, 1000, 2000, False, ntl.ZZ_pX([-5,0,1],5^1000), 'big', 'e',ntl.ZZ_pX([1],5^1000))
sage: a = ntl.ZZ_pX([4,2],5^2)
sage: b = ntl.ZZ_pX([6,3],5^2)
sage: A._get_modulus_test(a, b, 2)
[4 24]
sage: a * b
[24 24 6]
sage: mod(6 * 5 + 24, 25)
4
Returns a ZZ_pContext for self.prime^self.prec_cap
TESTS:
sage: PC = PowComputer_ext_maker(5, 5, 10, 20, False, ntl.ZZ_pX([-5,0,1],5^10), 'FM', 'e',ntl.ZZ_pX([1],5^10))
sage: PC._get_top_context_test()
NTL modulus 9765625
Multiplies a and b modulo the modulus corresponding to self.polynomial() (mod self.prime^self.prec_cap)
EXAMPLES:
sage: A = PowComputer_ext_maker(5, 3, 10, 20, False, ntl.ZZ_pX([-5,0,1],5^10), 'FM', 'e',ntl.ZZ_pX([1],5^10))
sage: a = ntl.ZZ_pX([129223,1231],5^10)
sage: b = ntl.ZZ_pX([289741,323],5^10)
sage: A._get_top_modulus_test(a, b)
[1783058 7785200]
sage: a*b
[9560618 7785200 397613]
sage: mod(397613 * 5 + 9560618, 5^10)
1783058
Restores the context for self.prime^((n-1) // self.e + 1)
EXAMPLES:
sage: PC = PowComputer_ext_maker(5, 5, 10, 20, False, ntl.ZZ_pX([-5,0,1],5^10), 'FM', 'e',ntl.ZZ_pX([1],5^10))
sage: PC._restore_context_capdiv_test(8) #indirect doctest
Restores the contest corresponding to self.prime^n
EXAMPLES:
sage: PC = PowComputer_ext_maker(5, 5, 10, 20, False, ntl.ZZ_pX([-5,0,1],5^10), 'FM', 'e',ntl.ZZ_pX([1],5^10))
sage: PC._restore_context_test(4)
Restores the context corresponding to self.prime^self.prec_cap
EXAMPLES:
sage: PC = PowComputer_ext_maker(5, 5, 10, 20, False, ntl.ZZ_pX([-5,0,1],5^10), 'FM', 'e',ntl.ZZ_pX([1],5^10))
sage: PC._restore_top_context_test()
Returns the polynomial (with coefficient precision prec_cap) associated to this PowComputer.
The polynomial is output as an ntl_ZZ_pX.
EXAMPLES:
sage: PC = PowComputer_ext_maker(5, 5, 10, 20, False, ntl.ZZ_pX([-5,0,1],5^10), 'FM', 'e',ntl.ZZ_pX([1],5^10))
sage: PC.polynomial()
[9765620 0 1]
Runs a speed test.
INPUT:
n -- input to a function to be tested (the function needs to be set in the source code).
runs -- The number of runs of that function
OUTPUT:
The time in seconds that it takes to call the function on n, runs times.
sage: PC = PowComputer_ext_maker(5, 10, 10, 20, False, ntl.ZZ_pX([-5, 0, 1], 5^10), 'small', 'e',ntl.ZZ_pX([1],5^10))
sage: PC.speed_test(10, 10^6) # random
0.0090679999999991878
This class only caches a context and modulus for p^prec_cap.
Designed for use with fixed modulus p-adic rings, in Eisenstein and unramified extensions of $mathbb{Z}_p$.
This class computes and stores low_shifter and high_shifter, which aid in right shifting elements.
Accessor function for high_shifter, which are the polynomials used to shift right.
These polynomials are used to shift by amounts greater than the degree of the defining polynomial, but less than e*prec_cap.
EXAMPLES:
sage: A = PowComputer_ext_maker(5, 3, 10, 40, False, ntl.ZZ_pX([-5,75,15,0,1],5^10), 'FM', 'e',ntl.ZZ_pX([1,-15,-3],5^10))
sage: A._high_shifter(0)
[263296 51990 228 3465]
If we take this and multiply by x^4, and reduce modulo x^4 + 15*x^2 + 75*x - 5, we should get 5.
sage: R.<x> = ZZ[]
sage: f = 263296 + 51990*x + 228*x^2 + 3465*x^3
sage: g = x^4 + 15*x^2 + 75*x - 5
sage: f*x^4 % g
5
sage: A._high_shifter(1)
[1420786 9298230 2217816 6212495]
Similarly:
sage: f = 1420786 + 9298230*x + 2217816*x^2 + 6212495*x^3
sage: h = f*x^8 % g; h
-1328125000000*x^3 + 2962646484375*x^2 + 22094970703125*x - 1466308593725
Here, we need to remember that we're working modulo 5^10:
sage: h[0].valuation(5), h[1].valuation(5), h[2].valuation(5), h[3].valuation(5)
(2, 12, 13, 13)
sage: (h[0] - 25).valuation(5)
12
Accessor function for low_shifter, which are the polynomials used to shift right.
These polynomials are used to shift by amounts less than the degree of the defining polynomial.
EXAMPLES:
sage: A = PowComputer_ext_maker(5, 3, 10, 40, False, ntl.ZZ_pX([-5,75,15,0,1],5^10), 'FM', 'e',ntl.ZZ_pX([1,-15,-3],5^10))
sage: A._low_shifter(0)
[75 15 0 1]
Note that if we multiply this by x and reduce using the relation that x^4 = 5 - 75x - 15x^2, we just get 5.
sage: A._low_shifter(1)
[1140 225 1 15]
This one's a bit less obvious, but if we multiply by x^2, we get 5 (modulo x^4 = 5 - 75x - 15x^2).
This class caches all contexts and moduli between 1 and cache_limit, and also caches for prec_cap. In addition, it stores a dictionary of contexts and moduli of
Returns the context dictionary.
EXAMPLES:
sage: A = PowComputer_ext_maker(5, 6, 10, 20, False, ntl.ZZ_pX([-5,0,1],5^10), 'big','e',ntl.ZZ_pX([1],5^10))
sage: P = A._get_context_test(8)
sage: A._context_dict()
{8: NTL modulus 390625}
Returns the context dictionary.
EXAMPLES:
sage: A = PowComputer_ext_maker(5, 6, 10, 20, False, ntl.ZZ_pX([-5,0,1],5^10), 'big','e',ntl.ZZ_pX([1],5^10))
sage: P = A._get_context_test(8)
sage: A._modulus_dict()
{}
sage: a = ntl.ZZ_pX([4,2],5^8)
sage: b = ntl.ZZ_pX([6,3],5^8)
sage: A._get_modulus_test(a, b, 8)
[54 24]
sage: A._modulus_dict()
{8: NTL ZZ_pXModulus [390620 0 1] (mod 390625)}
Resets the dictionaries. Note that if there are elements lying around that need access to these dictionaries, calling this function and then doing arithmetic with those elements could cause trouble (if the context object gets garbage collected for example. The bugs introduced could be very subtle, because NTL will generate a new context object and use it, but there’s the potential for the object to be incompatible with the different context object).
EXAMPLES:
sage: A = PowComputer_ext_maker(5, 6, 10, 20, False, ntl.ZZ_pX([-5,0,1],5^10), 'big','e',ntl.ZZ_pX([1],5^10))
sage: P = A._get_context_test(8)
sage: A._context_dict()
{8: NTL modulus 390625}
sage: A.reset_dictionaries()
sage: A._context_dict()
{}
This class computes and stores low_shifter and high_shifter, which aid in right shifting elements. These are only stored at maximal precision: in order to get lower precision versions just reduce mod p^n.
Accessor function for high_shifter, which are the polynomials used to shift right.
These polynomials are used to shift by amounts greater than the degree of the defining polynomial, but less than e*prec_cap.
EXAMPLES:
sage: A = PowComputer_ext_maker(5, 3, 10, 40, False, ntl.ZZ_pX([-5,75,15,0,1],5^10), 'big', 'e',ntl.ZZ_pX([1,-15,-3],5^10))
sage: A._high_shifter(0)
[263296 51990 228 3465]
If we take this and multiply by x^4, and reduce modulo x^4 + 15*x^2 + 75*x - 5, we should get 5.
sage: R.<x> = ZZ[]
sage: f = 263296 + 51990*x + 228*x^2 + 3465*x^3
sage: g = x^4 + 15*x^2 + 75*x - 5
sage: f*x^4 % g
5
sage: A._high_shifter(1)
[1420786 9298230 2217816 6212495]
Similarly:
sage: f = 1420786 + 9298230*x + 2217816*x^2 + 6212495*x^3
sage: h = f*x^8 % g; h
-1328125000000*x^3 + 2962646484375*x^2 + 22094970703125*x - 1466308593725
Here, we need to remember that we're working modulo 5^10:
sage: h[0].valuation(5), h[1].valuation(5), h[2].valuation(5), h[3].valuation(5)
(2, 12, 13, 13)
sage: (h[0] - 25).valuation(5)
12
Accessor function for low_shifter, which are the polynomials used to shift right.
These polynomials are used to shift by amounts less than the degree of the defining polynomial.
EXAMPLES:
sage: A = PowComputer_ext_maker(5, 3, 10, 40, False, ntl.ZZ_pX([-5,75,15,0,1],5^10), 'big', 'e',ntl.ZZ_pX([1,-15,-3],5^10))
sage: A._low_shifter(0)
[75 15 0 1]
Note that if we multiply this by x and reduce using the relation that x^4 = 5 - 75x - 15x^2, we just get 5.
sage: A._low_shifter(1)
[1140 225 1 15]
This one's a bit less obvious, but if we multiply by x^2, we get 5 (modulo x^4 = 5 - 75x - 15x^2).
This class caches contexts and moduli densely between 1 and cache_limit. It requires cache_limit == prec_cap.
It is intended for use with capped relative and capped absolute rings and fields, in Eisenstein and unramified extensions of the base p-adic fields.
This class computes and stores low_shifter and high_shifter, which aid in right shifting elements. These are only stored at maximal precision: in order to get lower precision versions just reduce mod p^n.
Accessor function for high_shifter, which are the polynomials used to shift right.
These polynomials are used to shift by amounts greater than the degree of the defining polynomial, but less than e*prec_cap.
EXAMPLES:
sage: A = PowComputer_ext_maker(5, 10, 10, 40, False, ntl.ZZ_pX([-5,75,15,0,1],5^10), 'small', 'e',ntl.ZZ_pX([1,-15,-3],5^10))
sage: A._high_shifter(0)
[263296 51990 228 3465]
If we take this and multiply by x^4, and reduce modulo x^4 + 15*x^2 + 75*x - 5, we should get 5.
sage: R.<x> = ZZ[]
sage: f = 263296 + 51990*x + 228*x^2 + 3465*x^3
sage: g = x^4 + 15*x^2 + 75*x - 5
sage: f*x^4 % g
5
sage: A._high_shifter(1)
[1420786 9298230 2217816 6212495]
Similarly:
sage: f = 1420786 + 9298230*x + 2217816*x^2 + 6212495*x^3
sage: h = f*x^8 % g; h
-1328125000000*x^3 + 2962646484375*x^2 + 22094970703125*x - 1466308593725
Here, we need to remember that we're working modulo 5^10:
sage: h[0].valuation(5), h[1].valuation(5), h[2].valuation(5), h[3].valuation(5)
(2, 12, 13, 13)
sage: (h[0] - 25).valuation(5)
12
Accessor function for low_shifter, which are the polynomials used to shift right.
These polynomials are used to shift by amounts less than the degree of the defining polynomial.
EXAMPLES:
sage: A = PowComputer_ext_maker(5, 10, 10, 40, False, ntl.ZZ_pX([-5,75,15,0,1],5^10), 'small', 'e',ntl.ZZ_pX([1,-15,-3],5^10))
sage: A._low_shifter(0)
[75 15 0 1]
Note that if we multiply this by x and reduce using the relation that x^4 = 5 - 75x - 15x^2, we just get 5.
sage: A._low_shifter(1)
[1140 225 1 15]
This one's a bit less obvious, but if we multiply by x^2, we get 5 (modulo x^4 = 5 - 75x - 15x^2).
For pickling.
EXAMPLES:
sage: PC = PowComputer_ext_maker(5, 10, 10, 20, False, ntl.ZZ_pX([-5, 0, 1], 5^10), 'small', 'e',ntl.ZZ_pX([1],5^10)); PC
PowComputer_ext for 5, with polynomial [9765620 0 1]
sage: loads(dumps(PC))
PowComputer_ext for 5, with polynomial [9765620 0 1]
Returns a string representation of self.
EXAMPLES:
sage: PC = PowComputer_ext_maker(5, 10, 10, 20, False, ntl.ZZ_pX([-5, 0, 1], 5^10), 'small', 'e',ntl.ZZ_pX([1],5^10))
sage: PC # indirect doctest
PowComputer_ext for 5, with polynomial [9765620 0 1]
This function demonstrates a danger in using pow_ZZ_tmp.
EXAMPLES:
sage: PC = PowComputer_ext_maker(5, 5, 10, 20, False, ntl.ZZ_pX([-5,0,1],5^10), 'big', 'e',ntl.ZZ_pX([1],5^10))
When you cal pow_ZZ_tmp with an input that is not stored
(ie n > self.cache_limit and n != self.prec_cap),
it stores the result in self.temp_z and returns a pointer
to that ZZ_c. So if you try to use the results of two
calls at once, things will break.
sage: PC._pow_ZZ_tmp_demo(6, 8) # 244140625 on some architectures and 152587890625 on others: random
244140625
sage: 5^6*5^8
6103515625
sage: 5^6*5^6
244140625
Note that this does not occur if you try a stored value,
because the result of one of the calls points to that
stored value.
sage: PC._pow_ZZ_tmp_demo(6, 10)
152587890625
sage: 5^6*5^10
152587890625
Tests the pow_ZZ_tmp function
EXAMPLES:
sage: PC = PowComputer_ext_maker(5, 6, 6, 12, False, ntl.ZZ_pX([-5,0,1],5^6),'small', 'e',ntl.ZZ_pX([1],5^6))
sage: PC._pow_ZZ_tmp_test(4)
625
sage: PC._pow_ZZ_tmp_test(7)
78125
Tests the pow_ZZ_top function.
EXAMPLES:
sage: PC = PowComputer_ext_maker(5, 6, 6, 12, False, ntl.ZZ_pX([-5,0,1],5^6),'small', 'e',ntl.ZZ_pX([1],5^6))
sage: PC._pow_ZZ_top_test()
15625
Returns the precision cap of self, considered as a power of the uniformizer.
EXAMPLES:
sage: PC = PowComputer_ext_maker(5, 6, 6, 12, False, ntl.ZZ_pX([-5,0,1],5^5),'small', 'e',ntl.ZZ_pX([1],5^5))
sage: PC._ram_prec_cap()
12
Returns a PowComputer that caches the values $1, prime, prime^2, ldots, prime^cache_limit$.
Once you create a PowComputer, merely call it to get values out. You can input any integer, even if it’s outside of the precomputed range.
INPUT:
- prime -- An integer, the base that you want to exponentiate.
- cache_limit -- A positive integer that you want to cache
powers up to.
- prec_cap -- The cap on precisions of elements. For ramified
extensions, p^((prec_cap - 1) // e) will be the largest
power of p distinguishable from zero
- in_field -- Boolean indicating whether this PowComputer is
attached to a field or not.
- poly -- An ntl_ZZ_pX or ntl_ZZ_pEX defining the extension.
It should be defined modulo p^((prec_cap - 1) // e + 1)
- prec_type -- 'FM', 'small', or 'big', defining how caching
is done.
- ext_type -- 'u' = unramified, 'e' = Eisenstein, 't' =
two-step
- shift_seed -- (required only for Eisenstein and two-step)
For Eisenstein and two-step extensions, if f = a_n x^n - p
a_{n-1} x^{n-1} - ... - p a_0 with a_n a unit, then
shift_seed should be 1/a_n (a_{n-1} x^{n-1} + ... + a_0)
EXAMPLES:
sage: PC = PowComputer_ext_maker(5, 10, 10, 20, False, ntl.ZZ_pX([-5, 0, 1], 5^10), 'small','e',ntl.ZZ_pX([1],5^10))
sage: PC
PowComputer_ext for 5, with polynomial [9765620 0 1]
Shifts _a right _n x-adic digits, where x is considered modulo the polynomial in _shifter.
EXAMPLES:
sage: from sage.rings.padics.pow_computer_ext import ZZ_pX_eis_shift_test
sage: A = PowComputer_ext_maker(5, 3, 10, 40, False, ntl.ZZ_pX([-5,75,15,0,1],5^10), 'big', 'e',ntl.ZZ_pX([1,-15,-3],5^10))
sage: ZZ_pX_eis_shift_test(A, [0, 1], 1, 5)
[1]
sage: ZZ_pX_eis_shift_test(A, [0, 0, 1], 1, 5)
[0 1]
sage: ZZ_pX_eis_shift_test(A, [5], 1, 5)
[75 15 0 1]
sage: ZZ_pX_eis_shift_test(A, [1], 1, 5)
[]
sage: ZZ_pX_eis_shift_test(A, [17, 91, 8, -2], 1, 5)
[316 53 3123 3]
sage: ZZ_pX_eis_shift_test(A, [316, 53, 3123, 3], -1, 5)
[15 91 8 3123]
sage: ZZ_pX_eis_shift_test(A, [15, 91, 8, 3123], 1, 5)
[316 53 3123 3]