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