Given F=GF(q), create the finite additive abelian group A of order q=p^r that is the direct sum of r copies of the cyclic group of order p, together with a map from the field A to F that gives an isomorphism.
Given F=GF(q), create the multiplicative group of R as an abelian group. This returns the (additive) cyclic group A of order q - 1, together with a map from A to F - 0, sending 1 to a primitive element of F.
Create the enumerated set consisting of the elements of finite field F.
Given a finite field F that is an extension of degree n of E, define the natural isomorphism between F and the n-dimensional vector space E^n. The function returns two values:The basis of V is chosen to correspond with the power basis alpha^0, alpha^1, ..., alpha^(n - 1) of F, where alpha is the generator returned by Generator(F, E), so that V=E.1 x E.alpha x ... x E.alpha^(n - 1) and phi : alpha^i -> e_(i + 1), (for i = 0, ..., n - 1), where e_i is the basis vector of V having all components zero, except the i-th, which is one.
- (a)
- A vector space V isomorphic to E^n;
- (b)
- The isomorphism phi : F -> V.
Given a finite field F that is an extension of degree n of E, define the isomorphism between F and the n-dimensional vector space E^n defined by the basis B for F over E. The function returns two values:The basis of V is chosen to correspond with the basis B=beta_1, beta_2, ..., beta_(n) of F over E, as specified by the user, so that V=E.beta_1 x E.beta_2 x ... x E.beta_(n). phi : beta_i -> e_(i), (for i = 1, ..., n), where e_i is the basis vector of V having all components zero, except the i-th, which is one.
- (a)
- A vector space V isomorphic to E^n;
- (b)
- The isomorphism phi : F -> V.
Let F be a finite field that is an extension of degree n of E. The function returns two values:The matrix algebra A will be the subalgebra of the full algebra of n x n matrices over E generated by the companion matrix C of the defining polynomial of F over E. The generator Generator(F, E) of F over E is thus mapped to C.
- (a)
- A matrix algebra A of degree n, such that A is isomorphic to F;
- (b)
- An isomorphism phi : F -> A.
Let F be a finite field. Let A be a matrix algebra over F, and E be a subfield of F. The function returns two values:N is A considered as an E-matrix algebra.
- (a)
- A matrix algebra N over E isomorphic to A, obtained from A by expanding each component of an element of A into the block matrix associated with it;
- (b)
- An E-isomorphism phi : A -> N.
> F7 := FiniteField(7); > F49<w> := ext< F7 | 2 >; > F<z> := ext< F49 | 2 >; > v2, i2 := VectorSpace(F, F49); > v2; Full Vector space of degree 2 over GF(7^2) > i2(z^12); ( w w^28) > v4, i4 := VectorSpace(F, PrimeField(F)); > v4; Full Vector space of degree 4 over GF(7) > i4(z^12); (5 3 6 4)
The absolute degree of F, that is, the degree over its prime subfield.
Given a finite field F that has been constructed as an extension of a field E, return the degree of F over E.
Given a finite field F that has been constructed as an extension of a field E, return the polynomial with coefficients in E that was used to define F as an extension of E. This is the minimum polynomial of F.1.
Given a finite field F and a subfield E, return the polynomial with coefficients in E used to define F as an extension of E. This is the same as the minimum polynomial of the generator Generator(F, E) over E.
Given a finite field F and a positive integer m > 1, construct a polynomial P of degree m that is irreducible over F.A database of sparse irreducible polynomials over GF(2) has been constructed by Allan Steel for all degrees up to 11000. The call IrreduciblePolynomial(GF(2), m), for m within that range, will return the sparse polynomial of degree m from the database.
Given a finite field F and a positive integer m > 1, construct a polynomial P of degree m that is primitive over F. Thus, P is irreducible over F, and it has a primitive root of the degree m extension field of F as a root.
Given a finite field F and a positive integer m > 1, construct the set of all monic polynomials of degree m that are irreducible over F.
Given a prime p and an exponent n >= 1, return the Conway polynomial of degree n over GF(p). The Conway polynomial is defined in the introduction. Note that this polynomial is read in from a table containing Conway polynomials for a limited range of p, n only.
Given a prime p and an exponent n>1, return true and the Conway polynomial if it is known for the field GF(p), false otherwise.
Given a finite field F, this function returns true if F is defined over the prime field using the Conway polynomial, false otherwise.
Given a polynomial f over a finite field F, this function finds all roots of f in F, and returns a sorted sequence of tuples (pairs), each consisting of a root of f in F and its multiplicity.
Given a univariate polynomial f over a finite field K, compute the minimal splitting field S of f as an extension field of K, and return the roots of f in S, together with S. Using this function will be faster than computing the roots of f anew over the splitting field.
Given a univariate polynomial f over a finite field K, compute the minimal splitting field S of f as an extension field of K, and return the factorization (into linears) of f over S, together with S. Using this function will be faster than factorizing f anew over the splitting field.
Return a primitive n-th root of unity in the smallest possible extension field of K.
> K := GF(2);
> P<x> := PolynomialRing(GF(2));
> f := x^20 + x^11 + 1;
> Factorization(f);
[
<x^3 + x^2 + 1, 1>,
<x^8 + x^7 + x^3 + x^2 + 1, 1>,
<x^9 + x^7 + x^6 + x^4 + 1, 1>
]
> time r, S<w> := RootsInSplittingField(f);
Time: 0.450
We note that the splitting field S has degree 72 and there are 20 roots
of f in S of course. We check that the evaluation of f at each root
is zero.
> S;
Finite field of size 2^72
> DefiningPolynomial(S);
x^72 + x^10 + x^9 + x^3 + 1
> #r;
20
> r[1];
<w^71 + w^70 + w^67 + w^66 + w^65 + w^56 + w^55 + w^54 + w^52 + w^45 +
w^44 + w^42 + w^41 + w^38 + w^37 + w^35 + w^33 + w^32 + w^27 + w^24 +
w^22 + w^20 + w^19 + w^18 + w^16 + w^15 + w^6 + w^5 + w^4 + w^2 +
w + 1, 1>
> [IsZero(Evaluate(f, t[1])): t in r];
[ true, true, true, true, true, true, true, true, true, true, true, true,
true, true, true, true, true, true, true, true ]