Module: sage.rings.finite_field
Finite Fields support iteration, starting with 0.
sage: k = GF(9, 'a') sage: i = 0 sage: for x in k: print i, x; i+=1 0 0 1 1 2 2 3 a 4 a + 1 5 a + 2 6 2*a 7 2*a + 1 8 2*a + 2
Module-level Functions
order, [name=a]) |
Return a finite field of given order with generator labeled by the given name.
INPUT: order -- int name -- string (default: 'a')
sage: k, a = GF(9).objgen() sage: k Finite Field in a of size 3^2 sage: k.assign_names(['b']) sage: k Finite Field in b of size 3^2 sage: GF(9,'a') Finite Field in a of size 3^2
order, [name=a]) |
Synonym for FiniteField.
p, n) |
Return the Conway polynomial of degree n over GF(p), which is loaded from a table.
If the requested polynomial is not known, this function raises a RuntimeError exception.
INPUT: p -- int n -- int OUTPUT: Polynomial -- a polynomial over the prime finite field GF(p).
NOTE: The first time this function is called a table is read from disk, which takes a fraction of a second. Subsequent calls do not require reloading the table.
See also the ConwayPolynomials() object, which is a table of Conway polynomials. For example, if c=ConwayPolynomials, then c.primes() is a list of all primes for which the polynomials are known, and for a given prime p, c.degree(p) is a list of all degrees for which the Conway polynomials are known.
sage: conway_polynomial(2,5) x^5 + x^2 + 1 sage: conway_polynomial(101,5) x^5 + 2*x + 99 sage: conway_polynomial(97,101) Traceback (most recent call last): ... RuntimeError: Conway polynomial over F_97 of degree 101 not in database.
p, n) |
Return True if the Conway polynomial over F_p of degree n is in the database and False otherwise.
If the Conway polynomial is in the database, to obtain it use the command conway_polynomial(p,n).
sage: exists_conway_polynomial(2,3) True sage: exists_conway_polynomial(2,-1) False sage: exists_conway_polynomial(97,200) False sage: exists_conway_polynomial(6,6) False
x, F) |
INPUT: x -- gap finite field element F -- SAGE finite field OUTPUT: element of F
sage: x = gap('Z(13)') sage: F = GF(13) sage: F(x) 2 sage: F(gap('0*Z(13)')) 0 sage: F = GF(13^2) sage: x = gap('Z(13)') sage: F(x) 2 sage: x = gap('Z(13^2)^3') sage: F(x) 12*a + 11 sage: F.multiplicative_generator()^3 12*a + 11
Author: David Joyner and William Stein
x) |
x) |
Class: FiniteField_ext_pari
Create with the command FiniteField(order)
INPUT: q - int, prime power, order of the finite field name - string (default: 'a'), string for printing the generator
OUTPUT: FiniteField - finite field of order q.
sage: k = FiniteField(9, 'a') sage: k Finite Field in a of size 3^2 sage: k.is_field() True sage: k.characteristic() 3 sage: a = k.gen() sage: a a sage: a.parent() Finite Field in a of size 3^2 sage: a.charpoly() x^2 + 2*x + 2 sage: [a**i for i in range(8)] [1, a, a + 1, 2*a + 1, 2, 2*a, 2*a + 2, a + 2]
Fields can be coerced into sets or list and iterated over:
sage: list(k) [0, 1, 2, a, a + 1, a + 2, 2*a, 2*a + 1, 2*a + 2]
The following is a native Python set:
sage: set(k) set([a, 2*a + 1, a + 2, a + 1, 2*a + 2, 1, 0, 2, 2*a])
And the following is a SAGE enumerated set:
sage: EnumeratedSet(k) {a, 2*a + 1, a + 2, a + 1, 2*a + 2, 1, 0, 2, 2*a}
We can also make a list via comprehension:
sage: [x for x in k] [0, 1, 2, a, a + 1, a + 2, 2*a, 2*a + 1, 2*a + 2]
Next we compute with the finite field of order 16, where the name is named b.
sage: k16 = FiniteField(16, "b") sage: z = k16.gen() sage: z b sage: z.charpoly() x^4 + x + 1 sage: k16.is_field() True sage: k16.characteristic() 2 sage: z.multiplicative_order() 15
Of course one can also make prime finite fields.
sage: k = FiniteField(7)
Note that the generator is 1:
sage: k.gen() 1 sage: k.gen().multiplicative_order() 1
Illustration of dumping and loading:
sage: K = GF(7) sage: loads(K.dumps()) == K True sage: K = GF(7^10) sage: loads(K.dumps()) == K True sage: K = GF(7^10, 'a') sage: loads(K.dumps()) == K True
In this example
is large enough that Conway polynomials
are not used. Note that when the field is dumped the defining
polynomial
is also dumped. Since
is determined by a
random algorithm, it's important that
is dumped as part of
. If you quit SAGE and restart and remake a finite field
of the same order (and the order is large enough so that there
is no Conway polynomial), then defining polynomial is probably
different. However, if you load a previously saved field, that
will have the same defining polynomial.
sage: K = GF(10007^10) sage: loads(K.dumps()) == K True
self, q, [name=None], [modulus=a]) |
Create finite field of order q with variable printed as name.
INPUT: q -- integer, size of the finite field, not prime name -- (optional:default 'a') variable used for printing element of the finite field. Also, two finite fields are considered equal if they have the same variable name, and not otherwise. OUTPUT: FiniteField -- a finite field of order q with given variable name.
sage: FiniteField(17) Finite Field of size 17 sage: FiniteField(2^10) Finite Field in a of size 2^10 sage: FiniteField(3^5, "b") Finite Field in b of size 3^5 sage: FiniteField(3^5, "b").gen() b
You can also create a finite field using GF, which is a synonym for FiniteField.
sage: GF(19**2) Finite Field in a of size 19^2
Functions: characteristic,
degree,
gen,
is_prime,
is_prime_field,
modulus,
order,
polynomial
self) |
Returns the characteristic of the finite field, which is a prime int.
sage: k = FiniteField(3**4) sage: k.characteristic() 3
self) |
Returns the degree of the finite field, which is a positive integer.
sage: FiniteField(3).degree() 1 sage: FiniteField(3**20).degree() 20
self, [n=0]) |
Return chosen generator of the finite field. This generator is a root of the defining polynomial of the finite field, and is guaranteed to be a generator for the multiplicative group.
INPUT: nothing OUTPUT: FiniteFieldElement -- field generator of finite field
sage: FiniteField(2**4, "b").gen() b sage: k = FiniteField(3**4, "alpha") sage: a = k.gen() sage: a alpha sage: a**4 alpha^3 + 1
self) |
The number of elements of the finite field.
sage: k = GF(2**10) sage: k Finite Field in a of size 2^10 sage: k.order() 1024
self) |
Return the irreducible characteristic polynomial of the generator of this finite field, i.e., the polynomial f(x) so elements of the finite field as elements modulo f.
sage: k = FiniteField(17) sage: k.polynomial() x sage: k = FiniteField(9) sage: k.polynomial() x^2 + 2*x + 2
Special Functions: __call__,
__cmp__,
__len__,
__repr__,
_coerce_,
_pari_modulus,
_pari_one
self, x) |
Coerce x into the finite field.
INPUT: x -- object OUTPUT: FiniteFieldElement -- if possible, makes a finite field element from x.
sage: k = GF(3^4) sage: b = k(5) sage: b.parent() Finite Field in a of size 3^4 sage: a = k.gen() sage: k(a + 2) a + 2
Constant polynomials coerce into finite fields:
sage: R = QQ['x'] sage: k, a = GF(5^2).objgen() sage: k(R(2/3)) 4 sage: R, x = k['x'].objgen() sage: k(R(3)) 3
Nonconstant polynomials do not coerce:
sage: k(x) Traceback (most recent call last): ... TypeError: no coercion of non-constant polynomial x into Finite Field in a of size 5^2 defined. sage: k(R(a)) a
Multivariate polynomials also coerce:
sage: R = k['x,y,z']; R Polynomial Ring in x, y, z over Finite Field in a of size 5^2 sage: k(R(2)) 2 sage: R = QQ['x,y,z'] sage: k(R(1/5)) Traceback (most recent call last): ... TypeError: Unable to coerce 1/5 into Finite Field in a of size 5^2.
Note: Finite Fields are currently implemented using polynomials modulo p and the PARI ffinit function. In particular, we do not use Conway polynomials and do not yet define natural consistent inclusion maps between different finite fields.
Gap elements can also be coerced into finite fields.
sage: F = GF(8, 'a') sage: a = F.multiplicative_generator(); a a sage: b = gap(a^3); b Z(2^3)^3 sage: F(b) a + 1 sage: a^3 a + 1
sage: a = GF(13)(gap('0*Z(13)')); a 0 sage: a.parent() Finite Field of size 13
sage: F = GF(16) sage: F(gap('Z(16)^3')) a^3 sage: F(gap('Z(16)^2')) a^2
You can also call a finite extension field with a string to produce an element of that field, like this:
sage: k = GF(2^8, 'a') sage: k('a^200') a^4 + a^3 + a^2
This is especially useful for fast conversions from Singular etc. to FiniteFieldElements.
Author Log:
self, other) |
sage: GF(7)(2) == GF(7)(9) True sage: GF(7)(2) == GF(11)(2) False sage: GF(7)(2) == GF(8)(2) False sage: GF(7)(2) == 2 True
self) |
The number of elements of the finite field.
sage: k = GF(2**10) sage: k Finite Field in a of size 2^10 sage: len(k) 1024
self, x) |
Canonical coercion to self.
sage: GF(4)._coerce_(GF(2)(1)) 1 sage: GF(4)._coerce_(GF(4).0) a sage: GF(4)._coerce_(3) 1 sage: GF(4)._coerce_(2/3) Traceback (most recent call last): ... TypeError: no canonical coercion of 2/3 to Finite Field in a of size 2^2 sage: GF(8)._coerce_(GF(4).0) Traceback (most recent call last): ... TypeError: no canonical coercion of a to Finite Field in a of size 2^3 sage: GF(16)._coerce_(GF(4).0) Traceback (most recent call last): ... TypeError: no canonical coercion of a to Finite Field in a of size 2^4 defined; adding this is planned (see rings/finite_field.py to help!) sage: k = GF(8) sage: k._coerce_(GF(7)(2)) Traceback (most recent call last): ... TypeError: no canonical coercion of 2 to Finite Field in a of size 2^3
self) |
The polynomial mod p that defines the finite field, as a PARI object. This is implementation specific, and some finite fields might not be implemented using PARI, so you should avoid using this function.
INPUT: nothing OUTPUT: gen -- a pari polynomial gen
sage: GF(19**2, 'a')._pari_modulus() Mod(1, 19)*a^2 + Mod(18, 19)*a + Mod(2, 19)
sage: GF(13**3, 'a')._pari_modulus() Mod(1, 13)*a^3 + Mod(2, 13)*a + Mod(11, 13)
Note that the PARI modulus is always in terms of a, even if the field variable isn't. This is because the specific choice of variable name has meaning in PARI, i.e., it can't be arbitrary.
sage: FiniteField(2**4, "b")._pari_modulus() Mod(1, 2)*a^4 + Mod(1, 2)*a + Mod(1, 2)
self) |
The PARI object Mod(1,p). This is implementation specific and should be ignored by users.
Class: FiniteField_generic
self) |
sage: K = GF(7); K Finite Field of size 7 sage: loads(K.dumps()) == K True sage: GF(7^10) Finite Field in a of size 7^10 sage: K = GF(7^10, 'a'); K Finite Field in a of size 7^10 sage: loads(K.dumps()) == K True
Functions: cardinality,
gen,
is_field,
is_finite,
multiplicative_generator,
ngens,
order,
polynomial,
polynomial_ring,
random_element,
unit_group_exponent,
vector_space,
zeta,
zeta_order
self) |
Same as self.order().
self) |
Returns whether or not the finite field is a field, i.e., always returns True.
sage: k = FiniteField(3**4) sage: k.is_field() True
self) |
Return a generator for the multiplicative group of this field. The generator is not randomized, though it could change from one version of SAGE to another.
sage: k = GF(997) sage: k.multiplicative_generator() 7 sage: k = GF(11**3, name='a') sage: k.multiplicative_generator() a
self) |
The number of generators of the finite field. Always 1.
sage: k = FiniteField(3**4) sage: k.ngens() 1
self) |
Returns the polynomial ring over the prime subfield in the same variable as this finite field.
sage: k = FiniteField(3**4, "alpha") sage: k.polynomial_ring() Univariate Polynomial Ring in alpha over Finite Field of size 3
self, [bound=None]) |
A random element of the finite field.
INPUT: bound -- ignored
sage: k = GF(2**10, 'a') sage: k.random_element() a^9 + a
self) |
The exponent of the unit group of the finite field. For a finite field, this is always the order minus 1.
sage: k = GF(2**10) sage: k.order() 1024 sage: k.unit_group_exponent() 1023
self, [n=None]) |
Returns an element of multiplicative order n in this this finite field, if there is one. Raises a ValueError if there is not.
sage: k = GF(7) sage: k.zeta() 3 sage: k.zeta().multiplicative_order() 6 sage: k.zeta(3) 2 sage: k.zeta(3).multiplicative_order() 3 sage: k = GF(49) sage: k.zeta().multiplicative_order() 48 sage: k.zeta(6) 3
Special Functions: __cmp__,
__iter__,
_gap_init_,
_latex_
self, other) |
Compares this finite field with other. Two finite fields are equal if and only if they have the same cardinality *and* the defining polynomials are the same.
sage: FiniteField(3**2) == FiniteField(3**3) False sage: FiniteField(3**2) == FiniteField(3**2) True sage: FiniteField(3**2,'beta') == FiniteField(3**2,'alpha') False sage: FiniteField(3**2,'beta') == FiniteField(3**2,'beta') True
Class: FiniteField_prime_modn
self, p, [name=None]) |
Functions: characteristic,
degree,
gen,
is_prime,
is_prime_field,
modulus,
order,
polynomial
self) |
Returns the degree of the finite field, which is a positive integer.
sage: FiniteField(3).degree() 1 sage: FiniteField(3**20).degree() 20
Special Functions: __iter__,
__repr__,
_coerce_,
_is_valid_homomorphism_