1%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
2%%
3%%  gf_element       LiDIA documentation
4%%
5%%  This file contains the documentation of the class gf_element
6%%
7%%  Copyright   (c)   1995-1999   by  LiDIA-Group
8%%
9%%  Author:  Detlef Anton, Thomas Pfahler
10%%
11
12\newcommand{\ff}{\mathit{ff}}
13
14
15%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
16
17\NAME
18
19\CLASS{gf_element} \dotfill an element over a finite field
20
21
22%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
23
24\ABSTRACT
25
26\code{gf_element} is a class that provides arithmetics over a finite field.  If the finite field
27is defined by a polynomial $f(X) \bmod p$, then a variable of type \code{gf_element} holds a
28representation of a field element by its polynomial representation.
29
30
31%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
32
33\DESCRIPTION
34
35A variable of type \code{gf_element} consists of an instance of type \code{galois_field}
36(indicating the field over which the element is defined) and the representation of the element.
37The internal representation varies for different classes of finite fields.  Currently, we
38distinguish finite prime fields, extension fields of odd characteristic, and extension fields of
39characteristic 2.  However, the interface of the class \code{gf_element} is completely
40independent of the internal representation.
41
42Let $e$ be an instance of type \code{gf_element}.  If $\ff = \code{$e$.get_field()}$ and $g$
43denotes the polynomial \code{$\ff$.irred_polynomial()}, then $e$ represents the element
44($\code{$e$.polynomial_rep()} \bmod g(X)) \in \bbfF_p[X]/(g(X)\bbfF_p[X])$, where $p =
45\code{$\ff$.characteristic()}$.
46
47
48%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
49
50\CONS
51
52\begin{fcode}{ct}{gf_element}{}
53  initializes the \code{gf_element} over a mainly useless dummy field.
54\end{fcode}
55
56\begin{fcode}{ct}{gf_element}{const galois_field & $K$}
57  constructs an element over the finite field $K$.  The element is initialized with zero.
58\end{fcode}
59
60\begin{fcode}{ct}{gf_element}{const gf_element & $e$}
61  constructs a copy of $e$.
62\end{fcode}
63
64\begin{fcode}{dt}{~gf_element}{}
65\end{fcode}
66
67
68%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
69
70\ACCS
71
72Let \code{e} be an instance of type \code{gf_element}.
73
74\begin{cfcode}{galois_field}{$e$.get_field}{}
75  returns the field over which the element \code{e} is defined.
76\end{cfcode}
77
78\begin{cfcode}{const Fp_polynomial &}{$e$.polynomial_rep}{}
79  returns the polynomial representation of the element \code{e}.
80\end{cfcode}
81
82
83%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
84
85\ASGN
86
87Let \code{e} be an instance of type \code{gf_element}.
88
89\begin{fcode}{void}{$e$.set_polynomial_rep}{const Fp_polynomial & $g$}
90  sets $e$ to the element $g \bmod \code{$e$.get_field().irred_polynomial()}$.
91\end{fcode}
92
93\begin{fcode}{void}{$e$.assign_zero}{}
94  $e \assign 0$.
95\end{fcode}
96
97\begin{fcode}{void}{$e$.assign_one}{}
98  $e \assign 1$.
99\end{fcode}
100
101\begin{fcode}{void}{$e$.assign_zero}{const galois_field & $f$}
102  $e$ is assigned the zero element of the field $\ff$.
103\end{fcode}
104
105\begin{fcode}{void}{$e$.assign_one}{const galois_field & $f$}
106  $e$ is assigned the element 1 of the field $\ff$.
107\end{fcode}
108
109\begin{fcode}{void}{$e$.assign}{const bigint & $a$}
110  $e$ is assigned the element $a \cdot 1$ of the field $\ff$.
111\end{fcode}
112
113The operator \code{=} is overloaded.  For efficiency reasons, the following function is also
114implemented:
115
116\begin{fcode}{void}{$e$.assign}{const gf_element & $a$}
117  $e \assign a$.
118\end{fcode}
119
120
121%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
122
123\ARTH
124
125Let \code{e} be an instance of type \code{gf_element}.
126
127The following operators are overloaded and can be used in exactly the same way as for machine
128types in C++ (e.g.~\code{int}) :
129
130\begin{center}
131  \code{(binary) +, -, *, /, +=, -=, *=, /=}\\
132\end{center}
133
134To avoid copying, these operations can also be performed by the following functions:
135
136\begin{fcode}{void}{add}{gf_element & $c$, const gf_element & $a$, const gf_element & $b$}
137  $c \assign a + b$.
138\end{fcode}
139
140\begin{fcode}{void}{add}{gf_element & $c$, const bigint & $a$, const gf_element & $b$}
141  $c \assign a \cdot 1 + b$ over the field \code{$b$.get_field()}.
142\end{fcode}
143
144\begin{fcode}{void}{add}{gf_element & $c$, const gf_element & $a$, const bigint & $b$}
145  $c \assign a + b \cdot 1$ over the field \code{$a$.get_field()}.
146\end{fcode}
147
148\begin{fcode}{void}{subtract}{gf_element & $c$, const gf_element & $a$, const gf_element & $b$}
149  $c \assign a - b$.
150\end{fcode}
151
152\begin{fcode}{void}{subtract}{gf_element & $c$, const bigint & $a$, const gf_element & $b$}
153  $c \assign a \cdot 1 - b$ over the field \code{$b$.get_field()}.
154\end{fcode}
155
156\begin{fcode}{void}{subtract}{gf_element & $c$, const gf_element & $a$, const bigint & $b$}
157  $c \assign a - b \cdot 1$ over the field \code{$a$.get_field()}.
158\end{fcode}
159
160\begin{fcode}{void}{multiply}{gf_element & $c$, const gf_element & $a$, const gf_element & $b$}
161  $c \assign a \cdot b$.
162\end{fcode}
163
164\begin{fcode}{void}{multiply}{gf_element & $c$, const bigint & $a$, const gf_element & $b$}
165  $c \assign a \cdot 1 \cdot b$ over the field \code{$b$.get_field()}.
166\end{fcode}
167
168\begin{fcode}{void}{multiply}{gf_element & $c$, const gf_element & $a$, const bigint & $b$}
169  $c \assign a \cdot b \cdot 1$ over the field \code{$a$.get_field()}.
170\end{fcode}
171
172\begin{fcode}{void}{divide}{gf_element & $c$, const gf_element & $a$, const gf_element & $b$}
173  $c \assign a / b$, if $b \neq 0$.  Otherwise the \LEH will be invoked.
174\end{fcode}
175
176\begin{fcode}{void}{divide}{gf_element & $c$, const bigint & $a$, const gf_element & $b$}
177  $c \assign (a \cdot 1) / b$ over the field \code{$b$.get_field()}, if $b \neq 0$.  Otherwise the \LEH
178  will be invoked.
179\end{fcode}
180
181\begin{fcode}{void}{divide}{gf_element & $c$, const gf_element & $a$, const bigint & $b$}
182  $c \assign a / (b \cdot 1)$ over the field \code{$a$.get_field()}, if $b \neq 0$.  Otherwise the \LEH
183  will be invoked.
184\end{fcode}
185
186\begin{fcode}{void}{$e$.negate}{}
187  $e \assign -e$.
188\end{fcode}
189
190\begin{fcode}{void}{negate}{gf_element & $a$, const gf_element & $b$}
191  $a \assign -b$.
192\end{fcode}
193
194\begin{fcode}{void}{$e$.multiply_by_2}{}
195  $e \assign 2 \cdot e$.
196\end{fcode}
197
198\begin{fcode}{void}{$e$.invert}{}
199  $e \assign e^{-1}$, if $e \neq 0$.
200Otherwise the \LEH will be invoked.
201\end{fcode}
202
203\begin{fcode}{void}{invert}{gf_element & $a$, const gf_element & $b$}
204  $a \assign b^{-1}$, if $b \neq 0$.  Otherwise the \LEH will be invoked.
205\end{fcode}
206
207\begin{fcode}{gf_element}{inverse}{const gf_element & $a$}
208  returns $a^{-1}$, if $a \neq 0$.  Otherwise the \LEH will be invoked.
209\end{fcode}
210
211\begin{fcode}{gf_element}{sqrt}{const gf_element & $a$}
212  returns $x$ with $x^2 = a$.
213\end{fcode}
214
215\begin{fcode}{void}{square}{gf_element & $a$, const gf_element & $b$}
216  $a \assign b^2$.
217\end{fcode}
218
219\begin{fcode}{void}{power}{gf_element & $c$, const gf_element & $a$, const bigint & $e$}
220  $c \assign a^e$.
221\end{fcode}
222
223\begin{fcode}{void}{pth_power}{gf_element & $c$, const gf_element & $a$, lidia_size_t $e$}
224  $c \assign a^{p^e}$, where $p$ is the characteristic of the corresponding field.
225\end{fcode}
226
227
228%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
229
230\COMP
231
232Let \code{e} be an instance of type \code{gf_element}.
233
234The  binary operators \code{==},  \code{!=} are overloaded.
235
236\begin{cfcode}{bool}{$e$.is_zero}{}
237  returns \TRUE if $e = 0$, \FALSE otherwise.
238\end{cfcode}
239
240\begin{cfcode}{bool}{$e$.is_one}{}
241  returns \TRUE if $e = 1$, \FALSE otherwise.
242\end{cfcode}
243
244
245%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
246
247\BASIC
248
249Let \code{e} be an instance of type \code{gf_element}.
250
251\begin{fcode}{void}{$e$.randomize}{}
252  sets $e$ to a random element of the field \code{$e$.get_field()}.
253\end{fcode}
254
255\begin{fcode}{void}{$e$.randomize}{lidia_size_t $d$}
256  sets $e$ to a random element of the subfield $K$ of \code{$e$.get_field()}, where $K$ has
257  (absolute) degree $d$.  If $d$ is not a divisor of \code{$e$.get_field().degree()},
258  then the \LEH is invoked.
259\end{fcode}
260
261\begin{fcode}{void}{swap}{gf_element & $a$, gf_element & $b$}
262  swaps the values of $a$ and $b$.
263\end{fcode}
264
265\begin{fcode}{udigit}{hash}{const gf_element & $a$}
266  returns a hash value for $a$.
267\end{fcode}
268
269
270%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
271
272\HIGH
273
274Let $e$ be an instance of type \code{gf_element}.
275
276\begin{cfcode}{bigint}{$e$.order}{}
277  returns the order of $e$ in the multiplicative group of \code{$e$.get_field()}.
278\end{cfcode}
279% this might take some time because we might need to compute a factorization
280% of the order of the multiplicative group...
281
282\begin{cfcode}{multi_bigmod}{$e$.trace}{}
283  returns the trace of $e$.
284\end{cfcode}
285
286\begin{cfcode}{multi_bigmod}{$e$.norm}{}
287  returns the norm of $e$.
288\end{cfcode}
289
290\begin{cfcode}{bool}{$e$.is_square}{}
291  returns \TRUE if $e$ is a square, \FALSE otherwise.
292\end{cfcode}
293
294\begin{cfcode}{bool}{$e$.is_primitive_element}{}
295  checks whether the order of $e$ in the multiplicative group is $p^n-1$, where $p$ is the
296  characteristic and $n$ is the degree of the corresponding field.
297\end{cfcode}
298
299\begin{cfcode}{bool}{$e$.is_free_element}{}
300  checks whether $e$ is a free element, i.e. the generator of a normal base.
301\end{cfcode}
302
303\begin{fcode}{gf_element}{$e$.assign_primitive_element}{const galois_field & $\ff$}
304  sets $e$ to a generator of the multiplicative group of the field $\ff$.
305
306  \code{$e$.assign_primitive_element($ff$)} recomputes a generator on each
307  call and therefore is likely to return different values on subsequent
308  calls. If you don't need different values on each call, then
309  \code{galois_field::generator()} is more efficient.
310\end{fcode}
311
312\begin{cfcode}{unsigned int}{$e$.get_absolute_degree}{}
313  returns the extension degree $n$ of the current field over which $e$ is defined.
314\end{cfcode}
315
316\begin{cfcode}{unsigned int}{$e$.get_relative_degree}{}
317  returns the minimal extension degree $k$ of the field $\GF(p^k)$ over the prime field $\GF(p)$
318  such that $e$ is an element of $\GF(p^k)$ ($p$ denotes the characteristic of the corresponding
319  field).
320\end{cfcode}
321
322\begin{cfcode}{bigint}{$e$.lift_to_Z}{}
323  If $e$ is an element of a prime field $\GF(p)$ of characteristic $p$, then return the
324  least non negative residue of the residue class of the class $e \bmod p$.  Otherwise the \LEH is
325  invoked.
326\end{cfcode}
327
328\begin{fcode}{bool}{$e$.solve_quadratic}{const gf_element& $a_1$, const gf_element& $a_0$}
329  If the polynomial $X^2 + a_1 X + a_0$ has a root over the field over which $a_1$ and $a_0$ are
330  defined, then $e$ is set to a root and \TRUE is returned.  If the polynomial does not have a
331  root, \FALSE is returned.  If $a_1$ and $a_0$ are defined over different fields, the \LEH is
332  invoked.
333\end{fcode}
334
335
336%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
337
338\IO
339
340We distinguish between \emph{verbose} and \emph{short} I/O format.
341Let $e$ be an instance of type \code{gf_element}.  The verbose format
342is ``(g(X), f(X))'' where $g(X) = \code{$e$.polynomial_rep()}$ and
343$f(X) = \code{get_field().irred_polynomial()}$.  In case of a prime
344field $\GF(p)\cong\bbfZ/p\bbfZ$, the element $m \bmod p$ can also be
345written as \code{(m, p)}.
346
347For the short format, we assume that the finite field over which the
348element is defined is already known, i.e. if \code{$e$.get_field()}
349does not return the dummy field.  We distinguish the following cases,
350depending on the finite field, which we will denote by $K$:
351\begin{itemize}
352\item $K = \GF(p)$ is a prime field: ``\code{(m)}'' means the element
353$m\bmod p\in K$;
354\item $K = \GF(p^n), p \neq 2, n>1$: ``\code{(g(X))}'' means the
355element $g(X) \bmod \code{$K$.irred_polynomial()}$;
356\item $K = \GF(2^n)$, $n > 1$: ``\code{(Dec:$d$)}'', and
357``\code{(Hex:$d$)}'' mean the element $\sum_{i} a_i X^i \bmod 2$ for
358  $d = \sum_{i} a_i2^i$, where $d$ is an integer in decimal, or
359  hexadecimal representation, respectively.
360\item $K=GF(p^n)$: ``\code{$d$}'' means the
361element $(\sum_{i} a_i X^i) \bmod \code{$K$.irred_polynomial()}$ for
362  $d = \sum_{i} a_ip^i$, where $d$ is an integer in decimal.
363\end{itemize}
364
365%\begin{center}
366%\begin{tabular}{lll}
367%\code{(m)}    &$m\bmod p\in K$ &if $K=\GF(p)$ is a prime field\\
368%\code{(g(X))} &$g(X)\bmod {}$\code{K.irred_polynomial()}
369%                                       &if $K=\GF(p^n), p\neq2, n>1$\\
370%\code{(Dec:d)}        &$\sum\limits_{i} a_iX^i\bmod 2$ for
371%                                       $d=\sum\limits_{i}a_i2^i$
372%                                       &if $K=\GF(2^n), n>1$\\
373%\code{(Hex:d)}        &\multicolumn{2}{l}{analogously, only that \code{d} is expected in hexadecimal representation}
374%\end{tabular}
375%\end{center}
376
377The \code{istream} operator \code{>>} and the \code{ostream} operator \code{<<} are overloaded.
378
379\begin{fcode}{static void}{set_output_format}{unsigned int $m$}
380  sets the output format for all elements of the class \code{gf_element} to \emph{verbose} if
381  $m \neq 0$.  Otherwise the output format will be \emph{short}.
382\end{fcode}
383
384\begin{fcode}{unsigned int}{get_output_format}{}
385  returns 0, if the output format is set to ``short'', and 1 otherwise.
386\end{fcode}
387
388\begin{fcode}{istream &}{operator >>}{istream & in, gf_element & $e$}
389  reads an element of a finite field from \code{istream} \code{in}.  The input must be of the
390  format described above.  If the input is in the short format, the field over which the element
391  is defined must already be set beforehand, otherwise the \LEH is invoked.
392\end{fcode}
393
394\begin{fcode}{ostream &}{operator <<}{ostream & out, const gf_element & $e$}
395  writes the element $e$ to \code{ostream} \code{out} in verbose or short format, according
396  to \linebreak\code{gf_element::get_output_format()}.
397\end{fcode}
398
399
400%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
401
402\SEEALSO
403
404\SEE{galois_field}
405
406
407%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
408
409\EXAMPLES
410
411\begin{quote}
412\begin{verbatim}
413#include <LiDIA/gf_element.h>
414
415int main()
416{
417    bigint p;
418    lidia_size_t d;
419
420    cout << "Please enter the characteristic ";
421    cout << "of the finite field : "; cin >> p;
422    cout << "Please enter the degree of the ";
423    cout << "finite field : "; cin >> d;
424
425    galois_field field(p, d);
426    cout << "This field has ";
427    cout << field.number_of_elements();
428    cout <<" elements.\n";
429
430    cout << "The defining polynomial of the field is\n";
431    field.irred_polynomial().pretty_print();
432    cout << endl;
433
434    gf_element elem;
435    elem.assign_primitive_element(field);
436    cout << elem << " is a primitive element in this field.\n";
437
438    return 0;
439}
440\end{verbatim}
441\end{quote}
442
443
444%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
445
446\AUTHOR
447
448Detlef Anton, Franz-Dieter Berger, Stefan Neis, Thomas Pfahler
449