1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
|
#############################################################################
##
#W polyconw.gd GAP library Thomas Breuer
##
#H @(#)$Id: polyconw.gd,v 4.8.4.1 2005/04/13 11:45:39 gap Exp $
##
#Y Copyright (C) 1997, Lehrstuhl D fuer Mathematik, RWTH Aachen, Germany
#Y (C) 1998 School Math and Comp. Sci., University of St. Andrews, Scotland
#Y Copyright (C) 2002 The GAP Group
##
## This file contains the declaration of functions and data around
## Conway polynomials.
##
Revision.polyconw_gd :=
"@(#)$Id: polyconw.gd,v 4.8.4.1 2005/04/13 11:45:39 gap Exp $";
###############################################################################
##
#F PowerModEvalPol( <f>, <g>, <xpownmodf> )
##
## computes the coefficients list of the polynomial $g( x^n ) \bmod f$, for
## the given coefficients lists of the two polynomials $f$ and $g$, and the
## coefficients list of $x^n \bmod f$.
##
## We evaluate $g$ at $x^n \bmod f$, and use Horner\'s method and reduction
## modulo $f$ for computing the result.
## If $g = \sum_{i=0}^k g_i x^i$ then we compute
## $( \cdots (((c_k x^n + c_{k-1}) x^n + c_{k-2}) x^n + c_{k-3}) x^n
## + \cdots c_0$.
##
## (this function is used in `ConwayPol'.)
##
DeclareGlobalFunction( "PowerModEvalPol" );
############################################################################
##
#F ConwayPol( <p>, <n> ) . . . . . <n>-th Conway polynomial in charact. <p>
##
DeclareGlobalFunction( "ConwayPol" );
############################################################################
##
#F ConwayPolynomial( <p>, <n> ) . <n>-th Conway polynomial in charact. <p>
##
## is the Conway polynomial of the finite field $GF(p^n)$ as
## polynomial over the prime field in characteristic <p>.
##
## The *Conway polynomial* $\Phi_{n,p}$ of $GF(p^n)$ is defined by the
## following properties.
##
## First define an ordering of polynomials of degree $n$ over $GF(p)$ as
## follows. $f = \sum_{i=0}^n (-1)^i f_i x^i$ is smaller than
## $g = \sum_{i=0}^n (-1)^i g_i x^i$ if and only if there is an index
## $m \leq n$ such that $f_i = g_i$ for all $i > m$, and
## $\tilde{f_m} \< \tilde{g_m}$, where $\tilde{c}$ denotes the integer
## value in $\{ 0, 1, \ldots, p-1 \}$ that is mapped to $c\in GF(p)$ under
## the canonical epimorphism that maps the integers onto $GF(p)$.
##
## $\Phi_{n,p}$ is *primitive* over $GF(p)$ (see~"IsPrimitivePolynomial").
## That is, $\Phi_{n,p}$ is irreducible, monic,
## and is the minimal polynomial of a primitive root of $GF(p^n)$.
##
## For all divisors $d$ of $n$ the compatibility condition
## $\Phi_{d,p}( x^{\frac{p^n-1}{p^m-1}} ) \equiv 0 \pmod{\Phi_{n,p}(x)}$
## holds. (That is, the appropriate power of a zero of $\Phi_{n,p}$ is a
## zero of the Conway polynomial $\Phi_{d,p}$.)
##
## With respect to the ordering defined above, $\Phi_{n,p}$ shall be
## minimal.
##
## The computation of Conway polynomials can be time consuming. Therefore,
## {\GAP} comes with a list of precomputed polynomials. If a requested
## polynomial is not stored then {\GAP} prints a warning and computes it by
## checking all polynomials in the order defined above for the defining
## conditions. If $n$ is not a prime this is probably a very long computation.
## (Some previously known polynomials with prime $n$ are not stored in
## {\GAP} because they are quickly recomputed.) Use the function
## "IsCheapConwayPolynomial" to check in advance if `ConwayPolynomial' will
## give a result after a short time.
##
## Note that primitivity of a polynomial can only be checked if {\GAP} can
## factorize $p^n-1$. A sufficiently new version of the \package{FactInt}
## package contains many precomputed factors of such numbers from various
## factorization projects.
##
## See~\cite{L03} for further information on known Conway polynomials.
##
## If <pol> is a result returned by `ConwayPolynomial' the command
## `Print( InfoText( <pol> ) );' will print some info on the origin of that
## particular polynomial.
##
## For some purposes it may be enough to have any primitive polynomial for
## an extension of a finite field instead of the Conway polynomial,
## see~"ref:RandomPrimitivePolynomial" below.
##
DeclareGlobalFunction( "ConwayPolynomial" );
############################################################################
##
#F IsCheapConwayPolynomial( <p>, <n> ) . . . tell if Conway polynomial is cheap to obtain
##
## Returns `true' if `ConwayPolynomial( <p>, <n> )' will give a result in
## *reasonable* time. This is either the case when this polynomial is
## pre-computed, or if <n> is a not too big prime.
##
DeclareGlobalFunction( "IsCheapConwayPolynomial" );
############################################################################
##
#F RandomPrimitivePolynomial( <F>, <n>[, <i> ] ) . . . . . random primitive polynomial over finite field
##
## For a finite field <F> and a positive integer <n> this function
## returns a primitive polynomial of degree <n> over <F>, that is a zero of
## this polynomial has maximal multiplicative order $|<F>|^n-1$.
## If <i> is given then the polynomial is written in variable number <i>
## over <F> (see~"ref:Indeterminate"), the default for <i> is 1.
##
## Alternatively, <F> can be a prime power q, then <F> = GF(q) is assumed.
## And <i> can be a univariate polynomial over <F>, then the result is a
## polynomial in the same variable.
##
## This function can work for much larger fields than those for which
## Conway polynomials are available, of course {\GAP} must be able to
## factorize $|<F>|^n-1$.
##
DeclareGlobalFunction( "RandomPrimitivePolynomial" );
#############################################################################
##
#E
|
