# Finite residue fields#

We can take the residue field of maximal ideals in the ring of integers of number fields. We can also take the residue field of irreducible polynomials over $$\GF{p}$$.

EXAMPLES:

sage: # needs sage.rings.number_field
sage: x = polygen(ZZ, 'x')
sage: K.<a> = NumberField(x^3 - 7)
sage: P = K.ideal(29).factor()
sage: k = K.residue_field(P); k
Residue field in abar of Fractional ideal (2*a^2 + 3*a - 10)
sage: k.order()
841


We reduce mod a prime for which the ring of integers is not monogenic (i.e., 2 is an essential discriminant divisor):

sage: # needs sage.rings.number_field
sage: K.<a> = NumberField(x^3 + x^2 - 2*x + 8)
sage: F = K.factor(2); F
(Fractional ideal (-1/2*a^2 + 1/2*a - 1)) * (Fractional ideal (-a^2 + 2*a - 3))
* (Fractional ideal (3/2*a^2 - 5/2*a + 4))
sage: F.residue_field()
Residue field of Fractional ideal (-1/2*a^2 + 1/2*a - 1)
sage: F.residue_field()
Residue field of Fractional ideal (-a^2 + 2*a - 3)
sage: F.residue_field()
Residue field of Fractional ideal (3/2*a^2 - 5/2*a + 4)


We can also form residue fields from $$\ZZ$$:

sage: ZZ.residue_field(17)
Residue field of Integers modulo 17


And for polynomial rings over finite fields:

sage: # needs sage.rings.finite_rings
sage: R.<t> = GF(5)[]
sage: I = R.ideal(t^2 + 2)
sage: k = ResidueField(I); k
Residue field in tbar of Principal ideal (t^2 + 2) of
Univariate Polynomial Ring in t over Finite Field of size 5


AUTHORS:

• David Roe (2007-10-3): initial version

• William Stein (2007-12): bug fixes

• John Cremona (2008-9): extend reduction maps to the whole valuation ring add support for residue fields of ZZ

• David Roe (2009-12): added support for $$GF(p)(t)$$ and moved to new coercion framework.

class sage.rings.finite_rings.residue_field.LiftingMap#

Bases: Section

Lifting map from residue class field to number field.

EXAMPLES:

sage: # needs sage.rings.number_field
sage: x = polygen(ZZ, 'x')
sage: K.<a> = NumberField(x^3 + 2)
sage: F = K.factor(5).residue_field()
sage: F.degree()
2
sage: L = F.lift_map(); L
Lifting map:
From: Residue field in abar of Fractional ideal (a^2 + 2*a - 1)
To:   Maximal Order in Number Field in a with defining polynomial x^3 + 2
sage: L(F.0^2)
3*a + 1
sage: L(3*a + 1) == F.0^2
True

sage: # needs sage.rings.finite_rings
sage: R.<t> = GF(13)[]
sage: P = R.ideal(8*t^12 + 9*t^11 + 11*t^10 + 2*t^9 + 11*t^8
....:             + 3*t^7 + 12*t^6 + t^4 + 7*t^3 + 5*t^2 + 12*t + 1)
sage: k.<a> = P.residue_field()
sage: k.lift_map()
Lifting map:
From: Residue field in a of Principal ideal (t^12 + 6*t^11 + 3*t^10
+ 10*t^9 + 3*t^8 + 2*t^7 + 8*t^6 + 5*t^4 + 9*t^3 + 12*t^2 + 8*t + 5) of
Univariate Polynomial Ring in t over Finite Field of size 13
To:   Univariate Polynomial Ring in t over Finite Field of size 13

class sage.rings.finite_rings.residue_field.ReductionMap#

Bases: Map

A reduction map from a (subset) of a number field or function field to this residue class field.

It will be defined on those elements of the field with non-negative valuation at the specified prime.

EXAMPLES:

sage: # needs sage.rings.number_field sage.symbolic
sage: I = QQ[sqrt(17)].factor(5); I
Fractional ideal (5)
sage: k = I.residue_field(); k
Residue field in sqrt17bar of Fractional ideal (5)
sage: R = k.reduction_map(); R
Partially defined reduction map:
From: Number Field in sqrt17 with defining polynomial x^2 - 17
with sqrt17 = 4.123105625617660?
To:   Residue field in sqrt17bar of Fractional ideal (5)

sage: # needs sage.rings.finite_rings
sage: R.<t> = GF(next_prime(2^20))[]; P = R.ideal(t^2 + t + 1)
sage: k = P.residue_field()
sage: k.reduction_map()
Partially defined reduction map:
From: Fraction Field of
Univariate Polynomial Ring in t over Finite Field of size 1048583
To:   Residue field in tbar of Principal ideal (t^2 + t + 1) of
Univariate Polynomial Ring in t over Finite Field of size 1048583

section()#

Computes a section of the map, namely a map that lifts elements of the residue field to elements of the field.

EXAMPLES:

sage: # needs sage.rings.number_field
sage: x = polygen(ZZ, 'x')
sage: K.<a> = NumberField(x^5 - 5*x + 2)
sage: P = K.ideal(47).factor()
sage: k = K.residue_field(P)
sage: f = k.convert_map_from(K)
sage: s = f.section(); s
Lifting map:
From: Residue field in abar of
Fractional ideal (-14*a^4 + 24*a^3 + 26*a^2 - 58*a + 15)
To:   Number Field in a with defining polynomial x^5 - 5*x + 2
sage: s(k.gen())
a
sage: L.<b> = NumberField(x^5 + 17*x + 1)
sage: P = L.factor(53)
sage: l = L.residue_field(P)
sage: g = l.convert_map_from(L)
sage: s = g.section(); s
Lifting map:
From: Residue field in bbar of Fractional ideal (53, b^2 + 23*b + 8)
To:   Number Field in b with defining polynomial x^5 + 17*x + 1
sage: s(l.gen()).parent()
Number Field in b with defining polynomial x^5 + 17*x + 1

sage: # needs sage.rings.finite_rings
sage: R.<t> = GF(2)[]; h = t^5 + t^2 + 1
sage: k.<a> = R.residue_field(h)
sage: K = R.fraction_field()
sage: f = k.convert_map_from(K)
sage: f.section()                                                           # needs sage.libs.ntl
Lifting map:
From: Residue field in a of Principal ideal (t^5 + t^2 + 1) of
Univariate Polynomial Ring in t over Finite Field of size 2 (using GF2X)
To:   Fraction Field of
Univariate Polynomial Ring in t over Finite Field of size 2 (using GF2X)

class sage.rings.finite_rings.residue_field.ResidueFieldFactory#

Bases: UniqueFactory

A factory that returns the residue class field of a prime ideal $$p$$ of the ring of integers of a number field, or of a polynomial ring over a finite field.

INPUT:

• p – a prime ideal of an order in a number field.

• names – the variable name for the finite field created. Defaults to the name of the number field variable but with bar placed after it.

• check – whether or not to check if $$p$$ is prime.

OUTPUT:

The residue field at the prime $$p$$.

EXAMPLES:

sage: x = polygen(ZZ, 'x')
sage: K.<a> = NumberField(x^3 - 7)                                              # needs sage.rings.number_field
sage: P = K.ideal(29).factor()                                            # needs sage.rings.number_field
sage: ResidueField(P)                                                           # needs sage.rings.number_field
Residue field in abar of Fractional ideal (2*a^2 + 3*a - 10)


The result is cached:

sage: ResidueField(P) is ResidueField(P)                                        # needs sage.rings.number_field
True
sage: k = K.residue_field(P); k                                                 # needs sage.rings.number_field
Residue field in abar of Fractional ideal (2*a^2 + 3*a - 10)
sage: k.order()                                                                 # needs sage.rings.number_field
841


It also works for polynomial rings:

sage: R.<t> = GF(31)[]
sage: P = R.ideal(t^5 + 2*t + 11)
sage: ResidueField(P)                                                           # needs sage.rings.finite_rings
Residue field in tbar of Principal ideal (t^5 + 2*t + 11) of
Univariate Polynomial Ring in t over Finite Field of size 31

sage: ResidueField(P) is ResidueField(P)                                        # needs sage.rings.finite_rings
True
sage: k = ResidueField(P); k.order()                                            # needs sage.rings.finite_rings
28629151


An example where the generator of the number field doesn’t generate the residue class field:

sage: # needs sage.rings.number_field
sage: K.<a> = NumberField(x^3 - 875)
sage: P = K.ideal(5).factor(); k = K.residue_field(P); k
Residue field in abar of Fractional ideal (5, 1/25*a^2 - 2/5*a - 1)
sage: k.polynomial()
abar^2 + 3*abar + 4
sage: k.0^3 - 875
2


An example where the residue class field is large but of degree 1:

sage: # needs sage.rings.number_field
sage: K.<a> = NumberField(x^3 - 875)
sage: P = K.ideal(2007).factor(); k = K.residue_field(P); k
Residue field of Fractional ideal (223, 1/5*a + 11)
sage: k(a)
168
sage: k(a)^3 - 875
0


And for polynomial rings:

sage: # needs sage.rings.finite_rings
sage: R.<t> = GF(next_prime(2^18))[]
sage: P = R.ideal(t - 5)
sage: k = ResidueField(P); k
Residue field of Principal ideal (t + 262142) of
Univariate Polynomial Ring in t over Finite Field of size 262147
sage: k(t)
5


In this example, 2 is an inessential discriminant divisor, so divides the index of ZZ[a] in the maximal order for all a:

sage: # needs sage.rings.number_field
sage: K.<a> = NumberField(x^3 + x^2 - 2*x + 8)
sage: P = K.ideal(2).factor(); P
Fractional ideal (-1/2*a^2 + 1/2*a - 1)
sage: F = K.residue_field(P); F
Residue field of Fractional ideal (-1/2*a^2 + 1/2*a - 1)
sage: F(a)
0
sage: B = K.maximal_order().basis(); B
[1, 1/2*a^2 + 1/2*a, a^2]
sage: F(B)
1
sage: F(B)
0
sage: F
Residue field of Fractional ideal (-1/2*a^2 + 1/2*a - 1)
sage: F.degree()
1

create_key_and_extra_args(p, names=None, check=True, impl=None, **kwds)#

Return a tuple containing the key (uniquely defining data) and any extra arguments.

EXAMPLES:

sage: x = polygen(ZZ, 'x')
sage: K.<a> = NumberField(x^3 - 7)                                          # needs sage.rings.number_field
sage: ResidueField(K.ideal(29).factor())  # indirect doctest          # needs sage.rings.number_field
Residue field in abar of Fractional ideal (2*a^2 + 3*a - 10)

create_object(version, key, **kwds)#

Create the object from the key and extra arguments. This is only called if the object was not found in the cache.

EXAMPLES:

sage: x = polygen(ZZ, 'x')
sage: K.<a> = NumberField(x^3 - 7)                                          # needs sage.rings.number_field
sage: P = K.ideal(29).factor()                                        # needs sage.rings.number_field
sage: ResidueField(P) is ResidueField(P)  # indirect doctest                # needs sage.rings.number_field
True

class sage.rings.finite_rings.residue_field.ResidueFieldHomomorphism_global#

The class representing a homomorphism from the order of a number field or function field to the residue field at a given prime.

EXAMPLES:

sage: # needs sage.rings.number_field
sage: x = polygen(ZZ, 'x')
sage: K.<a> = NumberField(x^3 - 7)
sage: P  = K.ideal(29).factor()
sage: k  = K.residue_field(P)
sage: OK = K.maximal_order()
sage: abar = k(OK.1); abar
abar
sage: (1+abar)^179
24*abar + 12

sage: # needs sage.rings.number_field
sage: phi = k.coerce_map_from(OK); phi
Ring morphism:
From: Maximal Order in Number Field in a with defining polynomial x^3 - 7
To:   Residue field in abar of Fractional ideal (2*a^2 + 3*a - 10)
sage: phi in Hom(OK,k)
True
sage: phi(OK.1)
abar

sage: # needs sage.rings.finite_rings
sage: R.<t> = GF(19)[]; P = R.ideal(t^2 + 5)
sage: k.<a> = R.residue_field(P)
sage: f = k.coerce_map_from(R); f
Ring morphism:
From: Univariate Polynomial Ring in t over Finite Field of size 19
To:   Residue field in a of Principal ideal (t^2 + 5) of
Univariate Polynomial Ring in t over Finite Field of size 19

lift(x)#

Returns a lift of x to the Order, returning a “polynomial” in the generator with coefficients between 0 and $$p-1$$.

EXAMPLES:

sage: # needs sage.rings.number_field
sage: x = polygen(ZZ, 'x')
sage: K.<a> = NumberField(x^3 - 7)
sage: P = K.ideal(29).factor()
sage: k = K.residue_field(P)
sage: OK = K.maximal_order()
sage: f = k.coerce_map_from(OK)
sage: c = OK(a)
sage: b = k(a)
sage: f.lift(13*b + 5)
13*a + 5
sage: f.lift(12821*b + 918)
3*a + 19

sage: # needs sage.rings.finite_rings
sage: R.<t> = GF(17)[]; P = R.ideal(t^3 + t^2 + 7)
sage: k.<a> = P.residue_field(); f = k.coerce_map_from(R)
sage: f.lift(a^2 + 5*a + 1)
t^2 + 5*t + 1
sage: f(f.lift(a^2 + 5*a + 1)) == a^2 + 5*a + 1
True

section()#

Computes a section of the map, namely a map that lifts elements of the residue field to elements of the ring of integers.

EXAMPLES:

sage: # needs sage.rings.number_field
sage: x = polygen(ZZ, 'x')
sage: K.<a> = NumberField(x^5 - 5*x + 2)
sage: P = K.ideal(47).factor()
sage: k = K.residue_field(P)
sage: f = k.coerce_map_from(K.ring_of_integers())
sage: s = f.section(); s
Lifting map:
From: Residue field in abar of
Fractional ideal (-14*a^4 + 24*a^3 + 26*a^2 - 58*a + 15)
To:   Maximal Order in Number Field in a with defining polynomial x^5 - 5*x + 2
sage: s(k.gen())
a
sage: L.<b> = NumberField(x^5 + 17*x + 1)
sage: P = L.factor(53)
sage: l = L.residue_field(P)
sage: g = l.coerce_map_from(L.ring_of_integers())
sage: s = g.section(); s
Lifting map:
From: Residue field in bbar of Fractional ideal (53, b^2 + 23*b + 8)
To:   Maximal Order in Number Field in b
with defining polynomial x^5 + 17*x + 1
sage: s(l.gen()).parent()
Maximal Order in Number Field in b with defining polynomial x^5 + 17*x + 1

sage: # needs sage.rings.finite_rings
sage: R.<t> = GF(17)[]; P = R.ideal(t^3 + t^2 + 7)
sage: k.<a> = P.residue_field()
sage: f = k.coerce_map_from(R)
sage: f.section()
(map internal to coercion system -- copy before use)
Lifting map:
From: Residue field in a of Principal ideal (t^3 + t^2 + 7) of
Univariate Polynomial Ring in t over Finite Field of size 17
To:   Univariate Polynomial Ring in t over Finite Field of size 17

class sage.rings.finite_rings.residue_field.ResidueField_generic(p)#

Bases: Field

The class representing a generic residue field.

EXAMPLES:

sage: # needs sage.rings.number_field
sage: I = QQ[i].factor(2); I
Fractional ideal (I + 1)
sage: k = I.residue_field(); k
Residue field of Fractional ideal (I + 1)
sage: type(k)
<class 'sage.rings.finite_rings.residue_field.ResidueFiniteField_prime_modn_with_category'>

sage: # needs sage.rings.finite_rings
sage: R.<t> = GF(29)[]; P = R.ideal(t^2 + 2); k.<a> = ResidueField(P); k
Residue field in a of Principal ideal (t^2 + 2) of
Univariate Polynomial Ring in t over Finite Field of size 29
sage: type(k)                                                                   # needs sage.libs.linbox
<class 'sage.rings.finite_rings.residue_field_givaro.ResidueFiniteField_givaro_with_category'>

construction()#

Construction of this residue field.

OUTPUT:

An AlgebraicExtensionFunctor and the number field that this residue field has been obtained from.

The residue field is determined by a prime (fractional) ideal in a number field. If this ideal can be coerced into a different number field, then the construction functor applied to this number field will return the corresponding residue field. See github issue #15223.

EXAMPLES:

sage: # needs sage.rings.number_field
sage: K.<z> = CyclotomicField(7)
sage: P = K.factor(17)
sage: k = K.residue_field(P); k
Residue field in zbar of Fractional ideal (17)
sage: F, R = k.construction()
sage: F
AlgebraicExtensionFunctor
sage: R
Cyclotomic Field of order 7 and degree 6
sage: F(R) is k
True
sage: F(ZZ)
Residue field of Integers modulo 17
sage: F(CyclotomicField(49))
Residue field in zbar of Fractional ideal (17)

ideal()#

Return the maximal ideal that this residue field is the quotient by.

EXAMPLES:

sage: # needs sage.rings.number_field
sage: x = polygen(ZZ, 'x')
sage: K.<a> = NumberField(x^3 + x + 1)
sage: P = K.ideal(29).factor()
sage: k = K.residue_field(P)  # indirect doctest
sage: k.ideal() is P
True
sage: p = next_prime(2^40); p
1099511627791
sage: k = K.residue_field(K.prime_above(p))
sage: k.ideal().norm() == p
True

sage: # needs sage.rings.finite_rings
sage: R.<t> = GF(17)[]; P = R.ideal(t^3 + t^2 + 7)
sage: k.<a> = R.residue_field(P)
sage: k.ideal()
Principal ideal (t^3 + t^2 + 7) of
Univariate Polynomial Ring in t over Finite Field of size 17

lift(x)#

Returns a lift of x to the Order, returning a “polynomial” in the generator with coefficients between 0 and $$p-1$$.

EXAMPLES:

sage: # needs sage.rings.number_field
sage: x = polygen(ZZ, 'x')
sage: K.<a> = NumberField(x^3 - 7)
sage: P = K.ideal(29).factor()
sage: k = K.residue_field(P)
sage: OK = K.maximal_order()
sage: c = OK(a)
sage: b = k(a)
sage: k.lift(13*b + 5)
13*a + 5
sage: k.lift(12821*b + 918)
3*a + 19

sage: # needs sage.rings.finite_rings
sage: R.<t> = GF(17)[]; P = R.ideal(t^3 + t^2 + 7)
sage: k.<a> = P.residue_field()
sage: k.lift(a^2 + 5)
t^2 + 5

lift_map()#

Returns the standard map from this residue field up to the ring of integers lifting the canonical projection.

EXAMPLES:

sage: # needs sage.rings.number_field sage.symbolic
sage: I = QQ[3^(1/3)].factor(5); I
Fractional ideal (a - 2)
sage: k = I.residue_field(); k
Residue field of Fractional ideal (a - 2)
sage: f = k.lift_map(); f
Lifting map:
From: Residue field of Fractional ideal (a - 2)
To:   Maximal Order in Number Field in a with defining polynomial x^3 - 3
with a = 1.442249570307409?
sage: f.domain()
Residue field of Fractional ideal (a - 2)
sage: f.codomain()
Maximal Order in Number Field in a with defining polynomial x^3 - 3
with a = 1.442249570307409?
sage: f(k.0)
1

sage: # needs sage.rings.finite_rings
sage: R.<t> = GF(17)[]; P = R.ideal(t^3 + t^2 + 7)
sage: k.<a> = P.residue_field()
sage: f = k.lift_map(); f
(map internal to coercion system -- copy before use)
Lifting map:
From: Residue field in a of Principal ideal (t^3 + t^2 + 7) of
Univariate Polynomial Ring in t over Finite Field of size 17
To:   Univariate Polynomial Ring in t over Finite Field of size 17
sage: f(a^2 + 5)
t^2 + 5

reduction_map()#

Return the partially defined reduction map from the number field to this residue class field.

EXAMPLES:

sage: # needs sage.rings.number_field sage.symbolic
sage: I = QQ[2^(1/3)].factor(2); I
Fractional ideal (a)
sage: k = I.residue_field(); k
Residue field of Fractional ideal (a)
sage: pi = k.reduction_map(); pi
Partially defined reduction map:
From: Number Field in a with defining polynomial x^3 - 2
with a = 1.259921049894873?
To:   Residue field of Fractional ideal (a)
sage: pi.domain()
Number Field in a with defining polynomial x^3 - 2 with a = 1.259921049894873?
sage: pi.codomain()
Residue field of Fractional ideal (a)

sage: # needs sage.rings.number_field
sage: x = polygen(ZZ, 'x')
sage: K.<a> = NumberField(x^3 + x^2 - 2*x + 32)
sage: F = K.factor(2).residue_field()
sage: F.reduction_map().domain()
Number Field in a with defining polynomial x^3 + x^2 - 2*x + 32
sage: K.<a> = NumberField(x^3 + 128)
sage: F = K.factor(2).residue_field()
sage: F.reduction_map().codomain()
Residue field of Fractional ideal (1/4*a)

sage: # needs sage.rings.finite_rings
sage: R.<t> = GF(17)[]; P = R.ideal(t^3 + t^2 + 7)
sage: k.<a> = P.residue_field(); f = k.reduction_map(); f
Partially defined reduction map:
From: Fraction Field of Univariate Polynomial Ring in t
over Finite Field of size 17
To:   Residue field in a of Principal ideal (t^3 + t^2 + 7) of
Univariate Polynomial Ring in t over Finite Field of size 17
sage: f(1/t)
12*a^2 + 12*a

class sage.rings.finite_rings.residue_field.ResidueFiniteField_prime_modn(p, name, intp, to_vs, to_order, PB)#

The class representing residue fields of number fields that have prime order.

EXAMPLES:

sage: # needs sage.rings.number_field
sage: R.<x> = QQ[]
sage: K.<a> = NumberField(x^3 - 7)
sage: P = K.ideal(29).factor()
sage: k = ResidueField(P); k
Residue field of Fractional ideal (-a^2 - 2*a - 2)
sage: k.order()
29
sage: OK = K.maximal_order()
sage: c = OK(a)
sage: b = k(a)
sage: k.coerce_map_from(OK)(c)
16
sage: k(4)
4
sage: k(c + 5)
21
sage: b + c
3

sage: # needs sage.rings.finite_rings
sage: R.<t> = GF(7)[]; P = R.ideal(2*t + 3)
sage: k = P.residue_field(); k
Residue field of Principal ideal (t + 5) of
Univariate Polynomial Ring in t over Finite Field of size 7
sage: k(t^2)
4
sage: k.order()
7