%% for a long time these were red and blue by default, %% now black, but keep variables to overwrite \definecolor{FuncColor}{rgb}{0.0,0.0,0.0} %% strange name because of pdflatex bug: \definecolor{Chapter }{rgb}{0.0,0.0,0.0} \definecolor{DarkOlive}{rgb}{0.1047,0.2412,0.0064}
% write page numbers to a .pnr log file for online help \newwrite\pagenrlog \immediate\openout\pagenrlog =\jobname.pnr \immediate\write\pagenrlog{PAGENRS := [} \newcommand{\logpage}[1]{\protect\write\pagenrlog{#1, \thepage,}} %% were never documented, give conflicts with some additional packages
\newcommand{\GAP}{\textsf{GAP}}
%% nicer description environments, allows long labels \usepackage{enumitem} \setdescription{style=nextline}
\newpage\setcounter{page}{2}
{\small \section*{Copyright} \logpage{[ 0, 0, 1 ]}
{\copyright} 2020\texttt{\symbol{45}} by Frank L{\"u}beck
This package may be distributed under the terms and conditions of the GNU
Public License Version 3 or later, see \href{https://www.gnu.org/licenses} {\texttt{https://www.gnu.org/licenses}}. \mbox{}}\\[1cm]
{\small \section*{Colophon} \logpage{[ 0, 0, 2 ]}
This package implements the constructions in the paper \cite{StdFFCyc}, that is it provides relatively easy to reproduce generators of finite fields
and compatible generators of their multiplicative cyclic subgroups. \mbox{}}\\[1cm] \newpage
\section{\textcolor{Chapter }{Aim}}\label{sec:Overview} \logpage{[ 1, 1, 0 ]} \hyperdef{L}{X8599E5B885932EEC}{}
{
This \textsf{GAP}\texttt{\symbol{45}}package provides a reference implementation for the
standardized constructions of finite fields and generators of cyclic subgroups
defined in the article\cite{StdFFCyc}.
The main functions are \texttt{FF} (\ref{FF}) to construct the finite field of order $p^n$ and \texttt{StandardCyclicGenerator} (\ref{StandardCyclicGenerator}) to construct a standardized generator of the multiplicative subgroup of a
given order $m$ in such a finite field. The condition on $m$ is that it divides $p^n-1$ and that \textsf{GAP} can factorize this number. (The factorization of the multiplicative group
order $p^n-1$ is not needed.)
Each field of order $p^n$ comes with a natural $\mathbb{F}_p$\texttt{\symbol{45}}basis which is a subset of the natural basis of each
extension field of order $p^{nm}$. The union of these bases is a basis of the algebraic closure of $\mathbb{F}_p$. Each element of the algebraic closure can be identified by its degree $d$ over its prime field and a number $0 \leq k \leq p^d-1$ (see \texttt{SteinitzPair} (\ref{SteinitzPair})) or, equivalently, by a certain multivariate polynomial (see \texttt{AsPolynomial} (\ref{AsPolynomial:for elements in standard
finite fields})). This can be useful for transferring finite field elements between programs
which use the same construction of finite fields.
The standardized generators of multiplicative cyclic groups have a nice
compatibility property: There is a unique group isomorphism from the
multiplicative group $\bar{\mathbb{F}}_p^\times$ of the algebraic closure of the finite field with $p$ elements into the group of complex roots of unity whose order is not divisible
by $p$ which maps a standard generator of order $m$ to $\exp(2\pi i/m)$. In particular, the minimal polynomials of standard generators of order $p^n-1$ for all $n$ fulfill the same compatibility conditions as Conway polynomials (see \texttt{ConwayPolynomial} (\textbf{Reference: ConwayPolynomial})). This can provide an alternative for the lifts used by \texttt{BrauerCharacterValue} (\textbf{Reference: BrauerCharacterValue}) which works for a much wider set of finite field elements where Conway
polynomials are very difficult or impossible to compute.
A translation of existing Brauer character tables relative to the lift defined
by Conway polynomials to the lift defined by our \texttt{StandardCyclicGenerator} (\ref{StandardCyclicGenerator}) can be computed with \texttt{StandardValuesBrauerCharacter} (\ref{StandardValuesBrauerCharacter}), provided the relevant Conway polynomials are known.
The article\cite{StdFFCyc} also defines a standardized embedding of \textsf{GAP}s finite fields constructed with \texttt{GF} (\textbf{Reference: GF for field size}) into the algebraic closure of the prime field $\mathbb{F}_p$ constructed here. This is available with \texttt{StandardIsomorphismGF} (\ref{StandardIsomorphismGF}). }
\section{\textcolor{Chapter }{Definition of standard finite fields}}\label{sec:StdFFIntro} \logpage{[ 2, 1, 0 ]} \hyperdef{L}{X7F9D926586E030D9}{}
{
In \cite{StdFFCyc} we define for each prime $p$ and positive integer $n$ a standardized model for the finite field with $p^n$ elements. This is done by defining for each prime $r$ polynomials of degree $r$ which define recursively $r$\texttt{\symbol{45}}power extensions of the prime field $GF(p)$ and by combining these for all $r | n$ in a unique tower of extensions of finite fields where the successive degrees
are non\texttt{\symbol{45}}decreasing primes.
Relative to this tower of prime degree extensions the resulting field comes
with a natural basis over the prime field which we call the \emph{tower basis}. This construction has the nice property that whenever $n | m$ then the tower basis of the field with $p^n$ elements is a subset of the tower basis of the field with $p^m$ elements. (See \cite{StdFFCyc} for more details.)
Expressing elements as linear combination of the tower basis we define a
bijection from the elements in the field of order $p^n$ to the range \texttt{[0..p\texttt{\symbol{94}}n\texttt{\symbol{45}}1]}; we call the number assigned to an element its \emph{Steinitz number}.
Via this construction each element in the algebraic closure of $GF(p)$ can be identified by its degree $d$ over the prime field and its Steinitz number in the field with $p^d$ elements (we call this a \emph{Steinitz pair}).
Since arithmetic in simple algebraic extensions is more efficient than in
iterated extensions we construct the fields recursively as simple extensions,
and including information about the base change between the tower basis and
the basis given by the powers of the generator. }
\subsection{\textcolor{Chapter }{Constructing standard finite fields}}\logpage{[ 2, 2, 1 ]} \hyperdef{L}{X80DCBB4F84F04DDB}{}
{ \noindent\textcolor{FuncColor}{$\triangleright$\enspace\texttt{StandardFiniteField({\mdseries\slshape p, n})\index{StandardFiniteField@\texttt{StandardFiniteField}} \label{StandardFiniteField}
}\hfill{\scriptsize (function)}}\\ \noindent\textcolor{FuncColor}{$\triangleright$\enspace\texttt{FF({\mdseries\slshape p, n})\index{FF@\texttt{FF}} \label{FF}
}\hfill{\scriptsize (function)}}\\ \textbf{\indent Returns:\ }
a finite field
\noindent\textcolor{FuncColor}{$\triangleright$\enspace\texttt{StandardPrimeDegreePolynomial({\mdseries\slshape p, r, k})\index{StandardPrimeDegreePolynomial@\texttt{StandardPrimeDegreePolynomial}} \label{StandardPrimeDegreePolynomial}
}\hfill{\scriptsize (function)}}\\ \textbf{\indent Returns:\ }
a polynomial of degree \mbox{\texttt{\mdseries\slshape r}}
The arguments are a prime \mbox{\texttt{\mdseries\slshape p}} and a positive integer \mbox{\texttt{\mdseries\slshape n}}. The function \texttt{FF} (or its synomym \texttt{StandardFiniteField}) is one of the main functions of this package. It returns a standardized
field \texttt{F} of order $\mbox{\texttt{\mdseries\slshape p}}^{\mbox{\texttt{\mdseries\slshape n}}}$. It is implemented as a simple extension over the prime field \texttt{GF(p)} using \texttt{AlgebraicExtension} (\textbf{Reference: AlgebraicExtension})
The polynomials used for the prime degree extensions are accessible with \texttt{StandardPrimeDegreePolynomial}. For arguments \mbox{\texttt{\mdseries\slshape p, r, k}} it returns the irreducible polynomial of degree \mbox{\texttt{\mdseries\slshape r}} for the \mbox{\texttt{\mdseries\slshape k}}\texttt{\symbol{45}}th iterated extension of degree \mbox{\texttt{\mdseries\slshape r}} over the prime field. The polynomial is in the variable \texttt{x}\emph{r}\texttt{{\textunderscore}}\emph{k} and the coefficients can contain variables \texttt{x}\emph{r}\texttt{{\textunderscore}}\emph{l} with $l < k$.
These properties identify the finite fields constructed with \texttt{FF} (\ref{FF}). Prime fields constructed as \texttt{FF(p, 1)} have the property \texttt{IsStandardPrimeField}. They are identical with \texttt{GF(p)}, but calling them via \texttt{FF} (\ref{FF}) we store some additional information in these objects.
The fields constructed by \texttt{FF(p,k)} with \texttt{k} $ > 1$ have the property \texttt{IsStandardFiniteField}. Elements \mbox{\texttt{\mdseries\slshape x}} in such a field are in \texttt{IsStandardFiniteFieldElement}.
\section{\textcolor{Chapter }{Elements in standard finite fields}}\label{sec:ElementsFF} \logpage{[ 2, 3, 0 ]} \hyperdef{L}{X84ED04C57C4BB25B}{}
{
For fields in \texttt{IsStandardFiniteField} (\ref{IsStandardFiniteField}) we provide functions to map elements to their linear combination of the tower
basis, to their Steinitz number and Steinitz pair, or to their representing
multivariate polynomial with respect to all prime degree extensions, and vice
versa.
\subsection{\textcolor{Chapter }{Maps for elements of standard finite fields}}\logpage{[ 2, 3, 1 ]} \hyperdef{L}{X8569D7B1786AE5FC}{}
{ \noindent\textcolor{FuncColor}{$\triangleright$\enspace\texttt{AsVector({\mdseries\slshape a})\index{AsVector@\texttt{AsVector}!for elements in standard finite fields} \label{AsVector:for elements in standard finite fields}
}\hfill{\scriptsize (method)}}\\ \textbf{\indent Returns:\ }
a vector over prime field of \texttt{F}
\noindent\textcolor{FuncColor}{$\triangleright$\enspace\texttt{ElementVector({\mdseries\slshape F, v})\index{ElementVector@\texttt{ElementVector}} \label{ElementVector}
}\hfill{\scriptsize (method)}}\\ \textbf{\indent Returns:\ }
an element in \texttt{F}
\noindent\textcolor{FuncColor}{$\triangleright$\enspace\texttt{AsPolynomial({\mdseries\slshape a})\index{AsPolynomial@\texttt{AsPolynomial}!for elements in standard finite fields} \label{AsPolynomial:for elements in standard finite fields}
}\hfill{\scriptsize (method)}}\\ \textbf{\indent Returns:\ }
a polynomial in variables of the tower of \texttt{F}
\noindent\textcolor{FuncColor}{$\triangleright$\enspace\texttt{ElementPolynomial({\mdseries\slshape F, pol})\index{ElementPolynomial@\texttt{ElementPolynomial}} \label{ElementPolynomial}
}\hfill{\scriptsize (method)}}\\ \textbf{\indent Returns:\ }
an element in \texttt{F}
\noindent\textcolor{FuncColor}{$\triangleright$\enspace\texttt{SteinitzNumber({\mdseries\slshape a})\index{SteinitzNumber@\texttt{SteinitzNumber}} \label{SteinitzNumber}
}\hfill{\scriptsize (method)}}\\ \textbf{\indent Returns:\ }
an integer
\noindent\textcolor{FuncColor}{$\triangleright$\enspace\texttt{ElementSteinitzNumber({\mdseries\slshape F, nr})\index{ElementSteinitzNumber@\texttt{ElementSteinitzNumber}} \label{ElementSteinitzNumber}
}\hfill{\scriptsize (method)}}\\ \textbf{\indent Returns:\ }
an element in \texttt{F}
Here, \mbox{\texttt{\mdseries\slshape F}} is always a standard finite field (\texttt{IsStandardFiniteField} (\ref{IsStandardFiniteField})) and \mbox{\texttt{\mdseries\slshape a}} is an element of \mbox{\texttt{\mdseries\slshape F}}.
\texttt{AsVector} (\ref{AsVector:for elements in standard finite fields}) returns the coefficient vector of \mbox{\texttt{\mdseries\slshape a}} with respect to the tower basis of \mbox{\texttt{\mdseries\slshape F}}. And vice versa \texttt{ElementVector} returns the element of \mbox{\texttt{\mdseries\slshape F}} with the given coefficient vector.
Similarly, \texttt{AsPolynomial} (\ref{AsPolynomial:for elements in standard
finite fields}) returns the (reduced) polynomial in the indeterminates defining the tower of \mbox{\texttt{\mdseries\slshape F}}. Here, for each prime $r$ dividing the degree of the field the polynomial defining the $k$\texttt{\symbol{45}}th extension of degree $r$ over the prime field is written in the variable \texttt{x}$r$\texttt{{\textunderscore}}$k$. And \texttt{ElementPolynomial} returns the element of \mbox{\texttt{\mdseries\slshape F}} represented by the given polynomial (which does not need to be reduced).
Finally, \texttt{SteinitzNumber} returns the Steinitz number of \mbox{\texttt{\mdseries\slshape a}}. And \texttt{ElementSteinitzNumber} returns the element with given Steinitz number. \begin{Verbatim}[commandchars=!@|,fontsize=\small,frame=single,label=Example]
!gapprompt@gap>| !gapinput@F := FF(17, 12);|
FF(17, 12)
!gapprompt@gap>| !gapinput@a := PrimitiveElement(F);; a := a^11-3*a^5+a;|
ZZ(17,12,[0,1,0,0,0,14,0,0,0,0,0,1])
!gapprompt@gap>| !gapinput@v := AsVector(a);|
< immutable compressed vector length 12 over GF(17) >
!gapprompt@gap>| !gapinput@a = ElementVector(F, v);|
true
!gapprompt@gap>| !gapinput@ExtRepOfObj(a) = v * TowerBasis(F);|
true
!gapprompt@gap>| !gapinput@pol := AsPolynomial(a);;|
!gapprompt@gap>| !gapinput@ElementPolynomial(F, pol^10) = a^10;|
true
!gapprompt@gap>| !gapinput@nr := SteinitzNumber(a);|
506020624175737
!gapprompt@gap>| !gapinput@a = ElementSteinitzNumber(F, nr);|
true
!gapprompt@gap>| !gapinput@## primitive element of FF(17, 6)|
!gapprompt@gap>| !gapinput@y := ElementSteinitzNumber(F, 17^5);|
ZZ(17,12,[0,0,1,0,0,0,12,0,0,0,5,0])
!gapprompt@gap>| !gapinput@y = ValuePol([0,0,1,0,0,0,12,0,0,0,5,0], PrimitiveElement(F));|
true
!gapprompt@gap>| !gapinput@x6 := Indeterminate(FF(17,1), "x6");;|
!gapprompt@gap>| !gapinput@MinimalPolynomial(FF(17,1), y, x6) = DefiningPolynomial(FF(17,6));|
true \end{Verbatim}
}
}
\section{\textcolor{Chapter }{Embeddings of standard finite fields}}\label{sec:FFEmbed} \logpage{[ 2, 4, 0 ]} \hyperdef{L}{X7F3D740F80F68F74}{}
{
The tower basis of a standard finite field \texttt{F} contains the tower basis of any subfield. This yields a construction of
canonical embeddings of all subfields of \texttt{F} into \texttt{F}. And one can easily read off the smallest subfield containing an element in \texttt{F} from its coefficient vector with respect to the tower basis. Each element of
the algebraic closure of \texttt{FF(p,1)} is uniquely determined by its degree \texttt{d} and its Steinitz number in \texttt{FF(p, d)}.
\subsection{\textcolor{Chapter }{SteinitzPair}} \logpage{[ 2, 4, 1 ]}\nobreak \hyperdef{L}{X85BC2EF17DA2E707}{}
{\noindent\textcolor{FuncColor}{$\triangleright$\enspace\texttt{SteinitzPair({\mdseries\slshape a})\index{SteinitzPair@\texttt{SteinitzPair}} \label{SteinitzPair}
}\hfill{\scriptsize (operation)}}\\ \textbf{\indent Returns:\ }
a pair of integers
\noindent\textcolor{FuncColor}{$\triangleright$\enspace\texttt{SteinitzPair({\mdseries\slshape K, snr})\index{SteinitzPair@\texttt{SteinitzPair}!for Steinitz number} \label{SteinitzPair:for Steinitz number}
}\hfill{\scriptsize (method)}}\\ \textbf{\indent Returns:\ }
a pair of integers
The argument \mbox{\texttt{\mdseries\slshape a}} must be an element in \texttt{IsStandardFiniteFieldElement} (\ref{IsStandardFiniteFieldElement}). Then \texttt{SteinitzPair} returns a pair \texttt{[d, nr]} where \texttt{d} is the degree of \mbox{\texttt{\mdseries\slshape a}} over the prime field \texttt{FF(p, 1)} and \texttt{nr} is the Steinitz number of \mbox{\texttt{\mdseries\slshape a}} considered as element of \texttt{FF(p, d)}.
In the second variant a standard finite field \mbox{\texttt{\mdseries\slshape K}} is given and the Steinitz number of an element in \mbox{\texttt{\mdseries\slshape K}} and the result is the Steinitz pair of the corresponding element.
The inverse map is provided by a method for \texttt{SteinitzNumber} (\ref{SteinitzNumber:for Steinitz pair}) which gets a standard finite field and a Steinitz pair. \begin{Verbatim}[commandchars=!@|,fontsize=\small,frame=single,label=Example]
!gapprompt@gap>| !gapinput@F := FF(7, 360);|
FF(7, 360)
!gapprompt@gap>| !gapinput@t := ElementSteinitzNumber(F, 7^10);; # prim. elt of FF(7,12)|
!gapprompt@gap>| !gapinput@sp := SteinitzPair(t);|
[ 12, 117649 ]
!gapprompt@gap>| !gapinput@H := FF(7, 12);|
FF(7, 12)
!gapprompt@gap>| !gapinput@b := ElementSteinitzNumber(H, 117649);|
ZZ(7,12,[0,1,0,0,0,0,0,0,0,0,0,0])
!gapprompt@gap>| !gapinput@Value(MinimalPolynomial(FF(7,1), t), b);|
ZZ(7,12,[0])
!gapprompt@gap>| !gapinput@nr := SteinitzNumber(t);|
282475249
!gapprompt@gap>| !gapinput@nr = SteinitzNumber(F, sp);|
true
!gapprompt@gap>| !gapinput@sp = SteinitzPair(F, nr);|
true \end{Verbatim}
}
\subsection{\textcolor{Chapter }{Embedding (for standard finite fields)}} \logpage{[ 2, 4, 2 ]}\nobreak \hyperdef{L}{X851FD36881708D5E}{}
{\noindent\textcolor{FuncColor}{$\triangleright$\enspace\texttt{Embedding({\mdseries\slshape H, F})\index{Embedding@\texttt{Embedding}!for standard finite fields} \label{Embedding:for standard finite fields}
}\hfill{\scriptsize (method)}}\\ \textbf{\indent Returns:\ }
a field homomorphism
Let \mbox{\texttt{\mdseries\slshape F}} and \mbox{\texttt{\mdseries\slshape H}} be standard finite fields and \mbox{\texttt{\mdseries\slshape H}} be isomorphic to a subfield of \mbox{\texttt{\mdseries\slshape F}}. This function returns the canonical embedding of \mbox{\texttt{\mdseries\slshape H}} into \mbox{\texttt{\mdseries\slshape F}}.
\subsection{\textcolor{Chapter }{ZZ}} \logpage{[ 2, 4, 3 ]}\nobreak \hyperdef{L}{X800EE1C5800EE1C5}{}
{\noindent\textcolor{FuncColor}{$\triangleright$\enspace\texttt{ZZ({\mdseries\slshape p, n, coeffs})\index{ZZ@\texttt{ZZ}} \label{ZZ}
}\hfill{\scriptsize (operation)}}\\ \noindent\textcolor{FuncColor}{$\triangleright$\enspace\texttt{ZZ({\mdseries\slshape p, n, ffe})\index{ZZ@\texttt{ZZ}!for IsFFE} \label{ZZ:for IsFFE}
}\hfill{\scriptsize (operation)}}\\ \textbf{\indent Returns:\ }
an element in \texttt{FF(\mbox{\texttt{\mdseries\slshape p}}, \mbox{\texttt{\mdseries\slshape n}})}
For a prime \mbox{\texttt{\mdseries\slshape p}}, positive integer \mbox{\texttt{\mdseries\slshape n}} and an integer list \mbox{\texttt{\mdseries\slshape coeffs}} this function returns the element in \texttt{FF(\mbox{\texttt{\mdseries\slshape p}}, \mbox{\texttt{\mdseries\slshape n}})} represented by the polynomial with coefficient list \mbox{\texttt{\mdseries\slshape coeffs}} modulo \mbox{\texttt{\mdseries\slshape p}}. Elements in standard finite fields are also printed in this way.
For convenience the third argument \mbox{\texttt{\mdseries\slshape ffe}} can be in `GF(p,n)` (see \texttt{GF} (\textbf{Reference: GF for characteristic and degree}) and \texttt{IsFFE} (\textbf{Reference: IsFFE})). This returns the image of \mbox{\texttt{\mdseries\slshape ffe}} under the \texttt{StandardIsomorphismGF} (\ref{StandardIsomorphismGF}) of \texttt{FF(\mbox{\texttt{\mdseries\slshape p}},\mbox{\texttt{\mdseries\slshape n}})}. \begin{Verbatim}[commandchars=!@|,fontsize=\small,frame=single,label=Example]
!gapprompt@gap>| !gapinput@x := ZZ(19,5,[1,2,3,4,5]);|
ZZ(19,5,[1,2,3,4,5])
!gapprompt@gap>| !gapinput@a := PrimitiveElement(FF(19,5));|
ZZ(19,5,[0,1,0,0,0])
!gapprompt@gap>| !gapinput@x = [1,2,3,4,5]*[a^0,a^1,a^2,a^3,a^4];|
true
!gapprompt@gap>| !gapinput@One(FF(19,5)); # elements in prime field abbreviated|
ZZ(19,5,[1])
!gapprompt@gap>| !gapinput@One(FF(19,5)) = ZZ(19,5,[1]);|
true
!gapprompt@gap>| !gapinput@ZZ(19,5,Z(19^5)); # zero of ConwayPolynomial(19,5)|
ZZ(19,5,[12,5,3,4,5]) \end{Verbatim}
}
\subsection{\textcolor{Chapter }{MoveToSmallestStandardField}} \logpage{[ 2, 4, 4 ]}\nobreak \hyperdef{L}{X839220E3865258DA}{}
{\noindent\textcolor{FuncColor}{$\triangleright$\enspace\texttt{MoveToSmallestStandardField({\mdseries\slshape x})\index{MoveToSmallestStandardField@\texttt{MoveToSmallestStandardField}} \label{MoveToSmallestStandardField}
}\hfill{\scriptsize (function)}}\\ \noindent\textcolor{FuncColor}{$\triangleright$\enspace\texttt{\texttt{\symbol{92}}+({\mdseries\slshape x, y})\index{\texttt{\symbol{92}}+@\texttt{\texttt{\symbol{92}}+}!for standard finite field elements} \label{bSlash+:for standard finite field elements}
}\hfill{\scriptsize (method)}}\\ \noindent\textcolor{FuncColor}{$\triangleright$\enspace\texttt{\texttt{\symbol{92}}*({\mdseries\slshape x, y})\index{\texttt{\symbol{92}}*@\texttt{\texttt{\symbol{92}}*}!for standard finite field elements} \label{bSlash*:for standard finite field elements}
}\hfill{\scriptsize (method)}}\\ \noindent\textcolor{FuncColor}{$\triangleright$\enspace\texttt{\texttt{\symbol{92}}\texttt{\symbol{45}}({\mdseries\slshape x, y})\index{\texttt{\symbol{92}}\texttt{\symbol{45}}@\texttt{\texttt{\symbol{92}}\texttt{\symbol{45}}}!for standard finite field elements} \label{bSlash-:for standard finite field elements}
}\hfill{\scriptsize (method)}}\\ \noindent\textcolor{FuncColor}{$\triangleright$\enspace\texttt{\texttt{\symbol{92}}/({\mdseries\slshape x, y})\index{\texttt{\symbol{92}}/@\texttt{\texttt{\symbol{92}}/}!for standard finite field elements} \label{bSlash/:for standard finite field elements}
}\hfill{\scriptsize (method)}}\\ \textbf{\indent Returns:\ }
a field element
Here \mbox{\texttt{\mdseries\slshape x}} and \mbox{\texttt{\mdseries\slshape y}} must be elements in standard finite fields (of the same characteristic).
Then \texttt{MoveToSmallestStandardField} returns the element \mbox{\texttt{\mdseries\slshape x}} as element of the smallest possible degree extension over the prime field.
The arithmetic operations are even possible when \mbox{\texttt{\mdseries\slshape x}} and \mbox{\texttt{\mdseries\slshape y}} are not represented as elements in the same field. In this case the elements
are first mapped to the smallest field containing both. \begin{Verbatim}[commandchars=!@|,fontsize=\small,frame=single,label=Example]
!gapprompt@gap>| !gapinput@F := FF(1009,4);|
FF(1009, 4)
!gapprompt@gap>| !gapinput@G := FF(1009,6);|
FF(1009, 6)
!gapprompt@gap>| !gapinput@x := (PrimitiveElement(F)+One(F))^13;|
ZZ(1009,4,[556,124,281,122])
!gapprompt@gap>| !gapinput@y := (PrimitiveElement(G)+One(G))^5;|
ZZ(1009,6,[1,5,10,10,5,1])
!gapprompt@gap>| !gapinput@x+y;|
ZZ(1009,12,[557,0,936,713,332,0,462,0,843,191,797,0])
!gapprompt@gap>| !gapinput@x-y;|
ZZ(1009,12,[555,0,73,713,677,0,97,0,166,191,212,0])
!gapprompt@gap>| !gapinput@x*y;|
ZZ(1009,12,[253,289,700,311,109,851,345,408,813,657,147,887])
!gapprompt@gap>| !gapinput@x/y;|
ZZ(1009,12,[690,599,714,648,184,217,563,130,251,675,73,782])
!gapprompt@gap>| !gapinput@z := -y + (x+y);|
ZZ(1009,12,[556,0,0,713,0,0,784,0,0,191,0,0])
!gapprompt@gap>| !gapinput@SteinitzPair(z);|
[ 4, 125450261067 ]
!gapprompt@gap>| !gapinput@x=z;|
true
!gapprompt@gap>| !gapinput@MoveToSmallestStandardField(z);|
ZZ(1009,4,[556,124,281,122]) \end{Verbatim}
}
\subsection{\textcolor{Chapter }{StandardIsomorphismGF}} \logpage{[ 2, 4, 5 ]}\nobreak \hyperdef{L}{X7ECCD8D27FBA9505}{}
{\noindent\textcolor{FuncColor}{$\triangleright$\enspace\texttt{StandardIsomorphismGF({\mdseries\slshape F})\index{StandardIsomorphismGF@\texttt{StandardIsomorphismGF}} \label{StandardIsomorphismGF}
}\hfill{\scriptsize (function)}}\\ \textbf{\indent Returns:\ }
a field isomorphism
The argument \mbox{\texttt{\mdseries\slshape F}} must be a standard finite field, say \texttt{FF(p,n)} such that \textsf{GAP} can generate \texttt{GF(p,n)}. This function returns the field isomorphism from \texttt{GF(p,n)} to \mbox{\texttt{\mdseries\slshape F}}, which sends \texttt{Z(p,n)} to the element with Steinitz pair computed by \texttt{SteinitzPairConwayGenerator} (\ref{SteinitzPairConwayGenerator}).
\section{\textcolor{Chapter }{Generators of multiplicative groups}}\label{sec:StdCyc} \logpage{[ 3, 1, 0 ]} \hyperdef{L}{X864390D67EA526FA}{}
{
The multiplicative group of each finite field is cyclic and so for each
divisor $m$ of its order there is a unique subgroup of order $m$.
In \cite{StdFFCyc} we define standardized generators $x_m$ of these cyclic groups in the standard finite fields described in chapter \ref{ch:StdFF} which fulfill the following compatibility condition: If $k | m$ then $x_m^{{m/k}} = x_k$.
The condition that $x_m$ can be computed is that $m$ can be factorized. (If we do not know the prime divisors of $m$ then we cannot show that a given element has order $m$.) Note that this means that we can compute $x_m$ in \texttt{FF(p,n)} when $m | (p^n -1)$ and we know the prime divisors of $m$, even when the factorization of $(p^n-1)$ is not known.
In the case that the factorization of $m = p^n-1$ is known the corresponding $x_m$ is a standardized primitive root of \texttt{FF(p,n)} that can be computed.
Let $l | n$ and set $m = p^n-1$ and $k = p^l-1$. Then $x_m$ and $x_k$ are the standard primitive roots of \texttt{FF(p,n)} and \texttt{FF(p,l)} (considered as subfield of \texttt{FF(p,n)}), respectively. The compatibity condition says that $x_m^{{m/k}} = x_k$. This shows that the minimal polynomials of $x_m$ and $x_k$ over the prime field fulfill the same compatibility conditions as Conway
polynomials (see \texttt{ConwayPolynomial} (\textbf{Reference: ConwayPolynomial}).
\subsection{\textcolor{Chapter }{StandardCyclicGenerator}} \logpage{[ 3, 1, 1 ]}\nobreak \hyperdef{L}{X79D3165F833F28DA}{}
{\noindent\textcolor{FuncColor}{$\triangleright$\enspace\texttt{StandardCyclicGenerator({\mdseries\slshape F[, m]})\index{StandardCyclicGenerator@\texttt{StandardCyclicGenerator}} \label{StandardCyclicGenerator}
}\hfill{\scriptsize (operation)}}\\ \noindent\textcolor{FuncColor}{$\triangleright$\enspace\texttt{StandardPrimitiveRoot({\mdseries\slshape F})\index{StandardPrimitiveRoot@\texttt{StandardPrimitiveRoot}} \label{StandardPrimitiveRoot}
}\hfill{\scriptsize (attribute)}}\\ \textbf{\indent Returns:\ }
an element of \mbox{\texttt{\mdseries\slshape F}} or \texttt{fail}
The argument \mbox{\texttt{\mdseries\slshape F}} must be a standard finite field (see \texttt{FF} (\ref{FF})) and \mbox{\texttt{\mdseries\slshape m}} a positive integer. If \mbox{\texttt{\mdseries\slshape m}} does not divide $|\mbox{\texttt{\mdseries\slshape F}}| - 1$ the function returns \texttt{fail}. Otherwise a standardized element $x_{\mbox{\texttt{\mdseries\slshape m}}}$ of order \mbox{\texttt{\mdseries\slshape m}} is returned, as described above.
The argument \mbox{\texttt{\mdseries\slshape m}} is optional, if not given its default value is $|\mbox{\texttt{\mdseries\slshape F}}| - 1$. In this case $x_{\mbox{\texttt{\mdseries\slshape m}}}$ can also be computed with the attribute \texttt{StandardPrimitiveRoot}. \begin{Verbatim}[commandchars=!@B,fontsize=\small,frame=single,label=Example]
!gapprompt@gap>B !gapinput@F := FF(67, 18); # Conway polynomial was hard to computeB
FF(67, 18)
!gapprompt@gap>B !gapinput@x := PrimitiveElement(F);B
ZZ(67,18,[0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0])
!gapprompt@gap>B !gapinput@xprim := StandardPrimitiveRoot(F);;B
!gapprompt@gap>B !gapinput@k := (Size(F)-1) / Order(x);B
6853662165340556076084083497526
!gapprompt@gap>B !gapinput@xm := StandardCyclicGenerator(F, Order(x));;B
!gapprompt@gap>B !gapinput@xm = xprim^k;B
true
!gapprompt@gap>B !gapinput@F := FF(23, 201); # factorization of (|F| - 1) not known B
FF(23, 201)
!gapprompt@gap>B !gapinput@m:=79*269*67939;B
1443771689
!gapprompt@gap>B !gapinput@(Size(F)-1) mod m;B
0
!gapprompt@gap>B !gapinput@OrderMod(23, m);B
201
!gapprompt@gap>B !gapinput@xm := StandardCyclicGenerator(F, m);;B
!gapprompt@gap>B !gapinput@IsOne(xm^m);B
true
!gapprompt@gap>B !gapinput@ForAll(Factors(m), r-> not IsOne(xm^(m/r)));B
true
!gapprompt@gap>B !gapinput@F := FF(7,48);B
FF(7, 48)
!gapprompt@gap>B !gapinput@K := FF(7,12);B
FF(7, 12)
!gapprompt@gap>B !gapinput@emb := Embedding(K, F);;B
!gapprompt@gap>B !gapinput@x := StandardPrimitiveRoot(F);;B
!gapprompt@gap>B !gapinput@y := StandardPrimitiveRoot(K);;B
!gapprompt@gap>B !gapinput@y^emb = x^((Size(F)-1)/(Size(K)-1));B
true
!gapprompt@gap>B !gapinput@v := Indeterminate(FF(7,1), "v");B
v
!gapprompt@gap>B !gapinput@px := MinimalPolynomial(FF(7,1), x, v);;B
!gapprompt@gap>B !gapinput@py := MinimalPolynomial(FF(7,1), y, v);;B
!gapprompt@gap>B !gapinput@Value(py, PowerMod(v, (Size(F)-1)/(Size(K)-1), px)) mod px;B
0*Z(7) \end{Verbatim}
}
}
}
\chapter{\textcolor{Chapter }{Utilities from the \textsf{StandardFF} package}}\label{ch:Utils} \logpage{[ 4, 0, 0 ]} \hyperdef{L}{X7B7EC1DC7BF3A7BD}{}
{
\section{\textcolor{Chapter }{A simple bijection on a range}}\label{sec:SimpleRand} \logpage{[ 4, 1, 0 ]} \hyperdef{L}{X7BFCD0EA853203E8}{}
{
\subsection{\textcolor{Chapter }{StandardAffineShift}} \logpage{[ 4, 1, 1 ]}\nobreak \hyperdef{L}{X85113F358019E11C}{}
{\noindent\textcolor{FuncColor}{$\triangleright$\enspace\texttt{StandardAffineShift({\mdseries\slshape q, i})\index{StandardAffineShift@\texttt{StandardAffineShift}} \label{StandardAffineShift}
}\hfill{\scriptsize (function)}}\\ \textbf{\indent Returns:\ }
an integer in range \texttt{[0..q\texttt{\symbol{45}}1]}
This function returns $(m \mbox{\texttt{\mdseries\slshape i}} + a) \textrm{ mod } \mbox{\texttt{\mdseries\slshape q}}$, where $m$ is the largest integer prime to \mbox{\texttt{\mdseries\slshape q}} and $\leq 4 \mbox{\texttt{\mdseries\slshape q}} / 5$, and a is the largest integer $\leq 2 \mbox{\texttt{\mdseries\slshape q}} / 3$.
For fixed $q$ this function provides a bijection on the range \texttt{[0..q\texttt{\symbol{45}}1]}. \begin{Verbatim}[commandchars=!@|,fontsize=\small,frame=single,label=Example]
!gapprompt@gap>| !gapinput@List([0..10], i-> StandardAffineShift(11, i));|
[ 7, 4, 1, 9, 6, 3, 0, 8, 5, 2, 10 ] \end{Verbatim}
}
\subsection{\textcolor{Chapter }{FindLinearCombination}} \logpage{[ 4, 2, 1 ]}\nobreak \hyperdef{L}{X7F1ABC6E83E257A3}{}
{\noindent\textcolor{FuncColor}{$\triangleright$\enspace\texttt{FindLinearCombination({\mdseries\slshape v, start})\index{FindLinearCombination@\texttt{FindLinearCombination}} \label{FindLinearCombination}
}\hfill{\scriptsize (function)}}\\ \textbf{\indent Returns:\ }
a pair \texttt{[serec, lk]} of a record and vector or \texttt{fail}
Repeated calls of this function build up a semiechelon basis from the given
arguments \mbox{\texttt{\mdseries\slshape v}} which must be row vectors. To initialize a computation the function is called
with a start vector \mbox{\texttt{\mdseries\slshape v}} and \texttt{false} as second argument. The return value is a pair \texttt{[serec, lk]} where \texttt{serec} is a record which collects data from the previous calls of the function and \texttt{lk} is a row vector which expresses \mbox{\texttt{\mdseries\slshape v}} as linear combination of the vectors from previous calls, or \texttt{fail} if there is no such linear combination. In the latter case the data in the
record is extended with the linearly independent vector \texttt{v}.
In the following example we show how to compute a divisor of the minimal
polynomial of a matrix. \begin{Verbatim}[commandchars=!@|,fontsize=\small,frame=single,label=Example]
!gapprompt@gap>| !gapinput@mat := Product(GeneratorsOfGroup(Sp(30,5)));;|
!gapprompt@gap>| !gapinput@x := Indeterminate(GF(5), "x");;|
!gapprompt@gap>| !gapinput@v := (mat^0)[1];;|
!gapprompt@gap>| !gapinput@b := FindLinearCombination(v, false);;|
!gapprompt@gap>| !gapinput@repeat|
!gapprompt@>| !gapinput@ v := v*mat;|
!gapprompt@>| !gapinput@ l := FindLinearCombination(v, b[1]);|
!gapprompt@>| !gapinput@until IsList(l[2]);|
!gapprompt@gap>| !gapinput@mp := Value(UnivariatePolynomial(GF(5),|
!gapprompt@>| !gapinput@ Concatenation(-l[2], [One(GF(5))])), x);|
x^30+Z(5)^3*x^29+Z(5)^3*x+Z(5)^0
!gapprompt@gap>| !gapinput@# equal to minimal polynomial because of degree|
!gapprompt@gap>| !gapinput@mp = Value(MinimalPolynomial(GF(5), mat), x);|
true \end{Verbatim}
}
The argument \mbox{\texttt{\mdseries\slshape coeffs}} must be a list of elements in a finite field with \mbox{\texttt{\mdseries\slshape q}} elements (or some subfield of it).
The function checks if the univariate polynomial $f$ with coefficient list \mbox{\texttt{\mdseries\slshape coeffs}} (ending with the leading coefficient) is irreducible over the field with \mbox{\texttt{\mdseries\slshape q}} elements.
The algorithm computes the greatest common divisor of $f$ with $X^{{q^i}} - X$ for $i = 1, 2, \ldots$ up to half of the degree of $f$. \begin{Verbatim}[commandchars=!@|,fontsize=\small,frame=single,label=Example]
!gapprompt@gap>| !gapinput@cs := Z(3)^0 * ConwayPol(3,8);|
[ Z(3), Z(3), Z(3), 0*Z(3), Z(3)^0, Z(3), 0*Z(3), 0*Z(3), Z(3)^0 ]
!gapprompt@gap>| !gapinput@IsIrreducibleCoeffList(cs, 3);|
true
!gapprompt@gap>| !gapinput@F := FF(17,4);; x := PrimitiveElement(F);;|
!gapprompt@gap>| !gapinput@cs := [x, x+x^0, 0*x, x^0];|
[ ZZ(17,4,[0,1,0,0]), ZZ(17,4,[1,1,0,0]), ZZ(17,4,[0]), ZZ(17,4,[1]) ]
!gapprompt@gap>| !gapinput@while not IsIrreducibleCoeffList(cs, 17^4) do|
!gapprompt@>| !gapinput@ cs[1] := cs[1] + One(F);|
!gapprompt@>| !gapinput@od;|
!gapprompt@gap>| !gapinput@cs;|
[ ZZ(17,4,[8,1,0,0]), ZZ(17,4,[1,1,0,0]), ZZ(17,4,[0]), ZZ(17,4,[1]) ] \end{Verbatim}
}
\subsection{\textcolor{Chapter }{FindConjugateZeroes}} \logpage{[ 4, 4, 1 ]}\nobreak \hyperdef{L}{X7E781D7B7CB1DFF4}{}
{\noindent\textcolor{FuncColor}{$\triangleright$\enspace\texttt{FindConjugateZeroes({\mdseries\slshape K, cpol, qq})\index{FindConjugateZeroes@\texttt{FindConjugateZeroes}} \label{FindConjugateZeroes}
}\hfill{\scriptsize (function)}}\\ \textbf{\indent Returns:\ }
a list of field elements
The arguments must be a finite field \mbox{\texttt{\mdseries\slshape K}}, a polynomial \mbox{\texttt{\mdseries\slshape cpol}} over \mbox{\texttt{\mdseries\slshape K}} (or its coefficient list) and the order \mbox{\texttt{\mdseries\slshape qq}} of a subfield of \mbox{\texttt{\mdseries\slshape K}}. The polynomial must have coeffcients in the subfield with \mbox{\texttt{\mdseries\slshape qq}} elements, must be irreducible over this subfield and split into linear factors
over \mbox{\texttt{\mdseries\slshape K}}. The function \texttt{FindConjugateZeroes} returns the list of zeroes of \mbox{\texttt{\mdseries\slshape cpol}} in \mbox{\texttt{\mdseries\slshape K}}. \begin{Verbatim}[commandchars=!@|,fontsize=\small,frame=single,label=Example]
!gapprompt@gap>| !gapinput@K := GF(67,18);|
GF(67^18)
!gapprompt@gap>| !gapinput@F := FF(67,18);|
FF(67, 18)
!gapprompt@gap>| !gapinput@p1 := DefiningPolynomial(K);;|
!gapprompt@gap>| !gapinput@p2 := DefiningPolynomial(F);;|
!gapprompt@gap>| !gapinput@lK := FindConjugateZeroes(K, p2, 67);;|
!gapprompt@gap>| !gapinput@lF := FindConjugateZeroes(F, p1, 67);;|
!gapprompt@gap>| !gapinput@Minimum(List(lF, SteinitzNumber));|
12274789318154414216760893584069 \end{Verbatim}
}
\subsection{\textcolor{Chapter }{ZeroesConway}} \logpage{[ 4, 4, 2 ]}\nobreak \hyperdef{L}{X7C00A74780A75A10}{}
{\noindent\textcolor{FuncColor}{$\triangleright$\enspace\texttt{ZeroesConway({\mdseries\slshape F})\index{ZeroesConway@\texttt{ZeroesConway}} \label{ZeroesConway}
}\hfill{\scriptsize (function)}}\\ \textbf{\indent Returns:\ }
a list of field elements
Here, \mbox{\texttt{\mdseries\slshape F}} must be a standard finite field, say of degree $n$ over the prime field with $p$ elements. This function returns the same as \texttt{FindConjugateZeroes(F, One(F)*ConwayPol(p, n), p)} (using a specific implementation).
\subsection{\textcolor{Chapter }{SteinitzPairConwayGenerator}} \logpage{[ 4, 4, 3 ]}\nobreak \hyperdef{L}{X784E128A811F5C91}{}
{\noindent\textcolor{FuncColor}{$\triangleright$\enspace\texttt{SteinitzPairConwayGenerator({\mdseries\slshape F})\index{SteinitzPairConwayGenerator@\texttt{SteinitzPairConwayGenerator}} \label{SteinitzPairConwayGenerator}
}\hfill{\scriptsize (function)}}\\ \textbf{\indent Returns:\ }
a pair of integers
For a standard finite field \mbox{\texttt{\mdseries\slshape F}} of order $q$ for which a Conway polynomial (see \texttt{ConwayPolynomial} (\textbf{Reference: ConwayPolynomial})) is known this function returns the \texttt{SteinitzPair} (\ref{SteinitzPair}) for the element of \mbox{\texttt{\mdseries\slshape F}} corresponding to \texttt{Z(q)} (which is by definition the zero of the Conway polynomial in \mbox{\texttt{\mdseries\slshape F}} with the smallest Steinitz number which is compatible with the choice in all
proper subfields).
The argument \mbox{\texttt{\mdseries\slshape base}} must be a multiplicative element and \mbox{\texttt{\mdseries\slshape x}} must lie in the cyclic group generated by \mbox{\texttt{\mdseries\slshape base}}. The third argument \mbox{\texttt{\mdseries\slshape m}} must be the order of \mbox{\texttt{\mdseries\slshape base}} or its factorization. If \mbox{\texttt{\mdseries\slshape m}} is not given, it is computed first. This function returns the discrete
logarithm, that is an integer $e$ such that \mbox{\texttt{\mdseries\slshape base}}$^e = $ \mbox{\texttt{\mdseries\slshape x}}.
If \mbox{\texttt{\mdseries\slshape m}} is prime then Shanks' algorithm is used (which needs $O(\sqrt{\mbox{\texttt{\mdseries\slshape m}}})$ space and time). Otherwise let \mbox{\texttt{\mdseries\slshape m}} $ = r l$ and $e = a + b r$ with $0 \leq a < r$. Then $a =$ \texttt{DLog}$(\mbox{\texttt{\mdseries\slshape base}}^l, \mbox{\texttt{\mdseries\slshape x}}^l, r)$ and $b = $ \texttt{DLog}$(\mbox{\texttt{\mdseries\slshape base}}^r, \mbox{\texttt{\mdseries\slshape x}}/\mbox{\texttt{\mdseries\slshape base}}^a, l)$.
This function is used for a method of \texttt{LogFFE} (\textbf{Reference: LogFFE}). \begin{Verbatim}[commandchars=!@|,fontsize=\small,frame=single,label=Example]
!gapprompt@gap>| !gapinput@F := FF(67, 12);|
FF(67, 12)
!gapprompt@gap>| !gapinput@st := SteinitzPairConwayGenerator(F);|
[ 12, 5118698034368952035290 ]
!gapprompt@gap>| !gapinput@z := ElementSteinitzNumber(F, st[2]);;|
!gapprompt@gap>| !gapinput@x := StandardPrimitiveRoot(F);;|
!gapprompt@gap>| !gapinput@DLog(z, x, Size(F)-1);|
231901568073107448223
!gapprompt@gap>| !gapinput@K := GF(67,12);|
GF(67^12)
!gapprompt@gap>| !gapinput@zz := Z(67^12);|
z
!gapprompt@gap>| !gapinput@LogFFE(zz^2+1, zz);|
1667375214152688471247 \end{Verbatim}
}
\subsection{\textcolor{Chapter }{InvModCoeffs}} \logpage{[ 4, 6, 1 ]}\nobreak \hyperdef{L}{X7E978CBD81D69FA2}{}
{\noindent\textcolor{FuncColor}{$\triangleright$\enspace\texttt{InvModCoeffs({\mdseries\slshape fcoeffs, gcoeffs})\index{InvModCoeffs@\texttt{InvModCoeffs}} \label{InvModCoeffs}
}\hfill{\scriptsize (operation)}}\\ \textbf{\indent Returns:\ }
a list of \texttt{fail}
The arguments \mbox{\texttt{\mdseries\slshape fcoeffs}} and \mbox{\texttt{\mdseries\slshape gcoeffs}} are coeffient lists of two polynomials $f$ and $g$. This operation returns the coefficient list of the inverse $f^{-1}$ modulo $g$, if $f$ and $g$ are coprime, and \texttt{fail} otherwise.
\subsection{\textcolor{Chapter }{BerlekampMassey}} \logpage{[ 4, 6, 2 ]}\nobreak \hyperdef{L}{X7CE85678790D8967}{}
{\noindent\textcolor{FuncColor}{$\triangleright$\enspace\texttt{BerlekampMassey({\mdseries\slshape u})\index{BerlekampMassey@\texttt{BerlekampMassey}} \label{BerlekampMassey}
}\hfill{\scriptsize (function)}}\\ \textbf{\indent Returns:\ }
a list of field elements
The argument \mbox{\texttt{\mdseries\slshape u}} is a list of elements in a field $F$. This function implements the Berlekamp\texttt{\symbol{45}}Massey algorithm
which returns the shortest sequence $c$ of elements in $F$ such that for each $i > l$, the length of $c$, we have $u[i] = \sum_{{j=1}}^l \mbox{\texttt{\mdseries\slshape u}}[i-j] c[j]$. \begin{Verbatim}[commandchars=!@|,fontsize=\small,frame=single,label=Example]
!gapprompt@gap>| !gapinput@x := Indeterminate(GF(23), "x");;|
!gapprompt@gap>| !gapinput@f := x^5 + Z(23)^16*x + Z(23)^12;;|
!gapprompt@gap>| !gapinput@u := List([1..50], i-> Value(x^i mod f, 0));;|
!gapprompt@gap>| !gapinput@c := BerlekampMassey(u);;|
!gapprompt@gap>| !gapinput@ForAll([6..50], i-> u[i] = Sum([1..5], j-> u[i-j]*c[j]));|
true
!gapprompt@gap>| !gapinput@-c;|
[ 0*Z(23), 0*Z(23), 0*Z(23), Z(23)^16, Z(23)^12 ] \end{Verbatim}
}
Here $x$ must be an element of an algebraic extension field $F/K$. ($K$ must be the \texttt{LeftActingDomain} (\textbf{Reference: LeftActingDomain}) of $F$). This function computes the minimal polynomial of \mbox{\texttt{\mdseries\slshape x}} over $K$ by applying the Berlekamp\texttt{\symbol{45}}Massey algorithm to the list of
traces of $\mbox{\texttt{\mdseries\slshape x}}^i$.
The second variant uses the algorithm by Shoup in \cite{ShoupMiPo}. \begin{Verbatim}[commandchars=!@|,fontsize=\small,frame=single,label=Example]
!gapprompt@gap>| !gapinput@x := Indeterminate(GF(23), "x");;|
!gapprompt@gap>| !gapinput@f := x^5 + Z(23)^16*x + Z(23)^12;;|
!gapprompt@gap>| !gapinput@F := AlgebraicExtension(GF(23), f);;|
!gapprompt@gap>| !gapinput@mp := MinimalPolynomialByBerlekampMassey(PrimitiveElement(F));;|
!gapprompt@gap>| !gapinput@Value(mp, x) = f;|
true
!gapprompt@gap>| !gapinput@mp = MinimalPolynomialByBerlekampMasseyShoup(PrimitiveElement(F));|
true \end{Verbatim}
}
}
\section{\textcolor{Chapter }{Brauer characters with respect to different lifts}}\label{sec:BrauerChar} \logpage{[ 4, 7, 0 ]} \hyperdef{L}{X7C69EBE885DA1B15}{}
{
Let $G$ be a finite group, $g \in G$, and $\rho: G \to GL(d,p^n)$be a representation over a finite field. The Brauer character value $\chi(g)$ of $\rho$ at $g$ is defined as the sum of the eigenvalues of $\rho(g)$ in the algebraic closure of $\mathbb{F}_p$ lifted to complex roots of unity.
The lift used by \texttt{BrauerCharacterValue} (\textbf{Reference: BrauerCharacterValue}) and in the computation of many Brauer character tables (available through the \textsf{CTblLib} package) is defined by Conway polynomials (see \texttt{ConwayPolynomial} (\textbf{Reference: ConwayPolynomial})): They define the primitive root \texttt{Z(q)} in \texttt{GF(q)} which is mapped to $\exp(2 \pi i / (q-1))$ (that is \texttt{E(q\texttt{\symbol{45}}1)} in \textsf{GAP}).
Another lift is defined by the function \texttt{StandardCyclicGenerator} (\ref{StandardCyclicGenerator}) provided by this package. Here, \texttt{StandardCyclicGenerator(F, m)} is mapped to $\exp(2 \pi i / m)$ (that is \texttt{E(m)} in \textsf{GAP}).
The following function translates between these two lifts.
\subsection{\textcolor{Chapter }{StandardValuesBrauerCharacter}} \logpage{[ 4, 7, 1 ]}\nobreak \hyperdef{L}{X86408E6883916C5D}{}
{\noindent\textcolor{FuncColor}{$\triangleright$\enspace\texttt{StandardValuesBrauerCharacter({\mdseries\slshape tab, bch})\index{StandardValuesBrauerCharacter@\texttt{StandardValuesBrauerCharacter}} \label{StandardValuesBrauerCharacter}
}\hfill{\scriptsize (function)}}\\ \textbf{\indent Returns:\ }
a Brauer character
The argument \mbox{\texttt{\mdseries\slshape tab}} must be a Brauer character table for which the Brauer characters are defined
with respect to the lift given by Conway polynomials. And \mbox{\texttt{\mdseries\slshape bch}} must be an irreducible Brauer character of this table.
The function \texttt{StandardValuesBrauerCharacter} recomputes the values corresponding to the lift given by \texttt{StandardCyclicGenerator} (\ref{StandardCyclicGenerator}), provided that the Conway polynomials for computing the Frobenius character
values of \mbox{\texttt{\mdseries\slshape bch}} are available. If Conway polynomials are missing the corresponding character
values are substituted by \texttt{fail}. If the result does not contain \texttt{fail} it is a class function which is Galois conjugate to \mbox{\texttt{\mdseries\slshape bch}} (see \texttt{GaloisCyc} (\textbf{Reference: GaloisCyc for a class function})).
The utility \texttt{IsGaloisInvariant} returns \texttt{true} if all Galois conjugates of \mbox{\texttt{\mdseries\slshape bch}} are Brauer characters in \mbox{\texttt{\mdseries\slshape tab}}. If this is the case then different lifts will permute the Galois conjugates
and all of them are Brauer characters with respect to any lift.
WARNING: The result of this function may not be a valid Brauer character for
the table \mbox{\texttt{\mdseries\slshape tab}} (that is an integer linear combination of irreducible Brauer characters in \mbox{\texttt{\mdseries\slshape tab}}). For a proper handling of several lifts the data structure of Brauer
character tables needs to be extended (it must refer to the lift), and then
the result of this function should return a Brauer character of another table
that refers to another lift. \begin{Verbatim}[commandchars=!@|,fontsize=\small,frame=single,label=Example]
!gapprompt@gap>| !gapinput@tab := BrauerTable("M", 19);|
BrauerTable( "M", 19 )
!gapprompt@gap>| !gapinput@# cannot translate some values to different lift|
!gapprompt@gap>| !gapinput@fail in AsList(StandardValuesBrauerCharacter(tab, Irr(tab)[16]));|
true
!gapprompt@gap>| !gapinput@# but table contains the irreducible Brauer characters for any lift|
!gapprompt@gap>| !gapinput@ForAll(Irr(tab), bch-> IsGaloisInvariant(tab, bch));|
true
!gapprompt@gap>| !gapinput@tab := BrauerTable("A18", 3);|
BrauerTable( "A18", 3 )
!gapprompt@gap>| !gapinput@# here different lifts lead to different Brauer character tables|
!gapprompt@gap>| !gapinput@bch := Irr(tab)[38];;|
!gapprompt@gap>| !gapinput@IsGaloisInvariant(tab, bch);|
false
!gapprompt@gap>| !gapinput@new := StandardValuesBrauerCharacter(tab, bch);;|
!gapprompt@gap>| !gapinput@fail in AsList(new);|
false
!gapprompt@gap>| !gapinput@Position(Irr(tab), new);|
fail \end{Verbatim}
}
The inverse of a lift is used to reduce character values in characteristic $0$ modulo a prime $p$. Choosing a lift is equivalent to choosing a $p$\texttt{\symbol{45}}modular system. \textsf{GAP} has the function \texttt{FrobeniusCharacterValue} (\textbf{Reference: FrobeniusCharacterValue}) which computes this reduction with respect to the lift defined by Conway
polynomials.
Here is the corresponding function with respect to the lift constructed in
this package. \subsection{\textcolor{Chapter }{Frobenius character values}}\logpage{[ 4, 7, 2 ]} \hyperdef{L}{X814BE20A81F82969}{}
{ \noindent\textcolor{FuncColor}{$\triangleright$\enspace\texttt{SmallestDegreeFrobeniusCharacterValue({\mdseries\slshape cyc, p})\index{SmallestDegreeFrobeniusCharacterValue@\texttt{Smallest}\-\texttt{Degree}\-\texttt{Frobenius}\-\texttt{Character}\-\texttt{Value}} \label{SmallestDegreeFrobeniusCharacterValue}
}\hfill{\scriptsize (function)}}\\ \textbf{\indent Returns:\ }
a positive integer or \texttt{fail}
\noindent\textcolor{FuncColor}{$\triangleright$\enspace\texttt{StandardFrobeniusCharacterValue({\mdseries\slshape cyc, F})\index{StandardFrobeniusCharacterValue@\texttt{StandardFrobeniusCharacterValue}} \label{StandardFrobeniusCharacterValue}
}\hfill{\scriptsize (function)}}\\ \textbf{\indent Returns:\ }
an element of \mbox{\texttt{\mdseries\slshape F}} or \texttt{fail}
The argument \mbox{\texttt{\mdseries\slshape cyc}} must be a cyclotomic whose conductor and denominator are not divisible by the
prime integer \mbox{\texttt{\mdseries\slshape p}} or the characteristic of the standard finite field \mbox{\texttt{\mdseries\slshape F}}.
The order of the multiplicative group of \mbox{\texttt{\mdseries\slshape F}} must be divisible by the conductor of \mbox{\texttt{\mdseries\slshape cyc}}.
Then \texttt{StandardFrobeniusCharacterValue} returns the image of \mbox{\texttt{\mdseries\slshape cyc}} in \mbox{\texttt{\mdseries\slshape F}} under the homomorphism which maps the root of unity \texttt{E(n)} to the \texttt{StandardCyclicGenerator} (\ref{StandardCyclicGenerator}) of order \texttt{n} in \mbox{\texttt{\mdseries\slshape F}}. If the conditions are not fulfilled the function returns \texttt{fail}.
The function \texttt{SmallestDegreeFrobeniusCharacterValue} returns the smallest degree of a field over the prime field of order \mbox{\texttt{\mdseries\slshape p}} containing the image of \mbox{\texttt{\mdseries\slshape cyc}}. \begin{Verbatim}[commandchars=!@|,fontsize=\small,frame=single,label=Example]
!gapprompt@gap>| !gapinput@SmallestDegreeFrobeniusCharacterValue(E(13), 19);|
12
!gapprompt@gap>| !gapinput@F := FF(19,12);|
FF(19, 12)
!gapprompt@gap>| !gapinput@x := StandardFrobeniusCharacterValue(E(13),F);;|
!gapprompt@gap>| !gapinput@x^13;|
ZZ(19,12,[1])
!gapprompt@gap>| !gapinput@x = StandardCyclicGenerator(F, 13);|
true
!gapprompt@gap>| !gapinput@cc := (E(13)+1/3)^4;;|
!gapprompt@gap>| !gapinput@xx := StandardFrobeniusCharacterValue(cc, F);;|
!gapprompt@gap>| !gapinput@xx = StandardFrobeniusCharacterValue(E(13)+1/3, F)^4;|
true \end{Verbatim}
}
}
\section{\textcolor{Chapter }{Known factorizations of multiplicative group orders}}\label{sec:FactorData} \logpage{[ 4, 8, 0 ]} \hyperdef{L}{X78ED090878CEE6AA}{}
{
This variable contains a list where for each prime $p < 10000$ the entry \texttt{CANFACT[p]} holds a list of integers $i$ such that the number $p^i-1$ (the order of the multiplicative group of the finite field \texttt{FF(p,i)}) can be factored by \textsf{GAP} in a short time. This is based on the enormous efforts to find factors of
numbers of this form, see \cite{BrentFactors}.
For $p < 10$ the range of considered exponents is $2 \leq i \leq 2000$, for $10 < p < 100$ it is $2 \leq i \leq 500$, and for $100 < p < 10000$ it is $2 \leq i \leq 100$.
These data describe (in May 2022) $112968$ pairs \texttt{p, i} such that \texttt{StandardPrimitiveRoot(FF(p,i))} can be computed in reasonable time. Only for $10858$ of these cases \textsf{GAP} knows or can easily compute the corresponding Conway polynomial (see \texttt{ConwayPolynomial} (\textbf{Reference: ConwayPolynomial})).
The current content of \texttt{CANFACT} was generated after updating the data in the \textsf{FactInt} package concerning factors of numbers of the form $a^n \pm 1$. If you want to use that list you should also update your \textsf{GAP} installation with: \begin{Verbatim}[commandchars=!@|,fontsize=\small,frame=single,label=Example]
FetchMoreFactors( "https://maths-people.anu.edu.au/~brent/ftp/factors/factors.gz",
false);
FetchMoreFactors( "http://myfactorcollection.mooo.com:8090/brentdata/May31_2022/factors.gz",
true); \end{Verbatim}
}
These function compute all fields in some range, sometimes with further data.
All functions return a list with some timings and print a
log\texttt{\symbol{45}}file in the current directory.
\texttt{AllPrimeDegreePolynomials} computes all irreducible polynomials of prime degree needed for the
--> --------------------
--> maximum size reached
--> --------------------
¤ Diese beiden folgenden Angebotsgruppen bietet das Unternehmen0.59Angebot
Wie Sie bei der Firma Beratungs- und Dienstleistungen beauftragen können
¤
Die Informationen auf dieser Webseite wurden
nach bestem Wissen sorgfältig zusammengestellt. Es wird jedoch weder Vollständigkeit, noch Richtigkeit,
noch Qualität der bereit gestellten Informationen zugesichert.
Bemerkung:
Die farbliche Syntaxdarstellung ist noch experimentell.
