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: K.<a> = NumberField(x^3-7)
sage: P = K.ideal(29).factor()[0][0]
sage: k = K.residue_field(P)
sage: 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: 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[0][0].residue_field()
Residue field of Fractional ideal (1/2*a^2 - 1/2*a + 1)
sage: F[1][0].residue_field()
Residue field of Fractional ideal (-a^2 + 2*a - 3)
sage: F[2][0].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: 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: sage.categories.map.Section

Lifting map from residue class field to number field.

EXAMPLES:

sage: K.<a> = NumberField(x^3 + 2)
sage: F = K.factor(5)[0][0].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: 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: sage.categories.map.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: I = QQ[sqrt(17)].factor(5)[0][0]; 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: 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: K.<a> = NumberField(x^5 - 5*x + 2)
sage: P = K.ideal(47).factor()[0][0]
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)[0][0]
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: 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()
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: sage.structure.factory.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: K.<a> = NumberField(x^3-7)
sage: P = K.ideal(29).factor()[0][0]
sage: ResidueField(P)
Residue field in abar of Fractional ideal (2*a^2 + 3*a - 10)

The result is cached:

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

It also works for polynomial rings:

sage: R.<t> = GF(31)[]
sage: P = R.ideal(t^5 + 2*t + 11)
sage: ResidueField(P)
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)
True
sage: k = ResidueField(P); k.order()
28629151

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

sage: K.<a> = NumberField(x^3-875)
sage: P = K.ideal(5).factor()[0][0]; 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: K.<a> = NumberField(x^3-875); P = K.ideal(2007).factor()[2][0]; 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: 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: K.<a> = NumberField(x^3 + x^2 - 2*x + 8); P = K.ideal(2).factor()[0][0]; 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])
1
sage: F(B[2])
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: K.<a> = NumberField(x^3-7)
sage: ResidueField(K.ideal(29).factor()[0][0]) # indirect doctest
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: K.<a> = NumberField(x^3-7)
sage: P = K.ideal(29).factor()[0][0]
sage: ResidueField(P) is ResidueField(P) # indirect doctest
True

class sage.rings.finite_rings.residue_field.ResidueFieldHomomorphism_global

Bases: sage.rings.morphism.RingHomomorphism

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: K.<a> = NumberField(x^3-7)
sage: P  = K.ideal(29).factor()[0][0]
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: 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: 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: K.<a> = NumberField(x^3-7)
sage: P = K.ideal(29).factor()[0][0]
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: 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: K.<a> = NumberField(x^5 - 5*x + 2)
sage: P = K.ideal(47).factor()[0][0]
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)[0][0]
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: 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: sage.rings.ring.Field

The class representing a generic residue field.

EXAMPLES:

sage: I = QQ[i].factor(2)[0][0]; 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: 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)
<class 'sage.rings.finite_rings.residue_field.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 trac ticket #15223.

EXAMPLES:

sage: K.<z> = CyclotomicField(7)
sage: P = K.factor(17)[0][0]
sage: k = K.residue_field(P)
sage: 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: K.<a> = NumberField(x^3 + x + 1)
sage: P = K.ideal(29).factor()[0][0]
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: 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: K.<a> = NumberField(x^3-7)
sage: P = K.ideal(29).factor()[0][0]
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: 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: I = QQ[3^(1/3)].factor(5)[1][0]; 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: 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: I = QQ[2^(1/3)].factor(2)[0][0]; 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: K.<a> = NumberField(x^3 + x^2 - 2*x + 32)
sage: F = K.factor(2)[0][0].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)[0][0].residue_field()
sage: F.reduction_map().codomain()
Residue field of Fractional ideal (1/4*a)

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_givaro(p, q, name, modulus, to_vs, to_order, PB)

Bases: sage.rings.finite_rings.residue_field.ResidueField_generic, sage.rings.finite_rings.finite_field_givaro.FiniteField_givaro

The class representing residue fields of number fields that have non-prime order strictly less than \(2^16\).

EXAMPLES:

sage: R.<x> = QQ[]
sage: K.<a> = NumberField(x^3-7)
sage: P = K.ideal(29).factor()[0][0]
sage: k =K.residue_field(P)
sage: k.degree()
2
sage: OK = K.maximal_order()
sage: c = OK(a)
sage: b = k(c)
sage: b*c^2
7
sage: b*c
13*abar + 5

sage: R.<t> = GF(7)[]; P = R.ideal(t^2 + 4)
sage: k.<a> = R.residue_field(P); type(k)
<class 'sage.rings.finite_rings.residue_field.ResidueFiniteField_givaro_with_category'>
sage: k(1/t)
5*a

class sage.rings.finite_rings.residue_field.ResidueFiniteField_ntl_gf2e(q, name, modulus, repr, p, to_vs, to_order, PB)

Bases: sage.rings.finite_rings.residue_field.ResidueField_generic, sage.rings.finite_rings.finite_field_ntl_gf2e.FiniteField_ntl_gf2e

The class representing residue fields with order a power of 2.

When the order is less than \(2^16\), givaro is used by default instead.

EXAMPLES:

sage: R.<x> = QQ[]
sage: K.<a> = NumberField(x^3-7)
sage: P = K.ideal(29).factor()[0][0]
sage: k =K.residue_field(P)
sage: k.degree()
2
sage: OK = K.maximal_order()
sage: c = OK(a)
sage: b = k(c)
sage: b*c^2
7
sage: b*c
13*abar + 5

sage: R.<t> = GF(2)[]; P = R.ideal(t^19 + t^5 + t^2 + t + 1)
sage: k.<a> = R.residue_field(P); type(k)
<class 'sage.rings.finite_rings.residue_field.ResidueFiniteField_ntl_gf2e_with_category'>
sage: k(1/t)
a^18 + a^4 + a + 1
sage: k(1/t)*t
1

class sage.rings.finite_rings.residue_field.ResidueFiniteField_pari_ffelt(p, characteristic, name, modulus, to_vs, to_order, PB)

Bases: sage.rings.finite_rings.residue_field.ResidueField_generic, sage.rings.finite_rings.finite_field_pari_ffelt.FiniteField_pari_ffelt

The class representing residue fields of number fields that have non-prime order at least \(2^16\).

EXAMPLES:

sage: K.<a> = NumberField(x^3-7)
sage: P = K.ideal(923478923).factor()[0][0]
sage: k = K.residue_field(P)
sage: k.degree()
2
sage: OK = K.maximal_order()
sage: c = OK(a)
sage: b = k(c)
sage: b+c
2*abar
sage: b*c
664346875*abar + 535606347
sage: k.base_ring()
Finite Field of size 923478923

sage: R.<t> = GF(5)[]; P = R.ideal(4*t^12 + 3*t^11 + 4*t^10 + t^9 + t^8 + 3*t^7 + 2*t^6 + 3*t^4 + t^3 + 3*t^2 + 2)
sage: k.<a> = P.residue_field()
sage: type(k)
<class 'sage.rings.finite_rings.residue_field.ResidueFiniteField_pari_ffelt_with_category'>
sage: k(1/t)
3*a^11 + a^10 + 3*a^9 + 2*a^8 + 2*a^7 + a^6 + 4*a^5 + a^3 + 2*a^2 + a

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

Bases: sage.rings.finite_rings.residue_field.ResidueField_generic, sage.rings.finite_rings.finite_field_prime_modn.FiniteField_prime_modn

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

EXAMPLES:

sage: R.<x> = QQ[]
sage: K.<a> = NumberField(x^3-7)
sage: P = K.ideal(29).factor()[1][0]
sage: k = ResidueField(P)
sage: 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: 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