1%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 2%% 3%% gf_poly_modulus.tex LiDIA documentation 4%% 5%% This file contains the documentation of the class poly_modulus 6%% 7%% Copyright (c) 1996 by LiDIA-Group 8%% 9%% Authors: Thomas Pfahler 10%% 11 12 13%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 14 15\NAME 16 17\CLASS{gf_poly_modulus} \dotfill class for efficient computations modulo 18polynomials over finite fields 19 20 21%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 22 23\ABSTRACT 24 25If you need to do a lot of arithmetic modulo a fixed \code{polynomial< gf_element >} $f$, build 26a \code{gf_poly_modulus} $F$ for $f$. This pre-computes information about $f$ that speeds up 27the computation a great deal, especially for large polynomials. 28 29 30%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 31 32\DESCRIPTION 33 34The pre-computations for variables of type \code{gf_poly_modulus} as well consist of evaluating 35special representations. For further description, see \cite{Pfahler_Thesis:1998}. 36 37 38%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 39 40\CONS 41 42\begin{fcode}{ct}{gf_poly_modulus}{} 43 no initialization is done; you must call the member-function \code{build()} (see below) before 44 using this \code{gf_poly_modulus} in one of the arithmetical functions. 45\end{fcode} 46 47\begin{fcode}{ct}{gf_poly_modulus}{const polynomial< gf_element > & $f$} 48 initializes for computations modulo $f$. 49\end{fcode} 50 51\begin{fcode}{dt}{~gf_poly_modulus}{} 52\end{fcode} 53 54 55%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 56 57\BASIC 58 59Let $F$ be of type \code{gf_poly_modulus}. 60 61\begin{fcode}{void}{$F$.build}{const polynomial< gf_element > & $f$} 62 initializes for computations modulo $f$. 63\end{fcode} 64 65 66%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 67 68\ACCS 69 70Let $F$ be of type \code{gf_poly_modulus}. 71 72\begin{cfcode}{const polynomial< gf_element > &}{$F$.modulus}{} 73 returns a constant reference to the polynomial for which $F$ was build. 74\end{cfcode} 75 76 77%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 78 79\ARTH 80 81As described in the section \code{polynomial< gf_element >}, each polynomial carries a reference 82to an element of type \code{galois_field} representing the finite field over which the 83polynomial is defined. Therefore, if the finite fields of the \code{const} arguments are not 84the same, the \LEH is invoked. The ``resulting'' polynomial receives the finite field of the 85``input'' polynomials. 86 87\begin{fcode}{void}{remainder}{polynomial< gf_element > & $g$, 88 const polynomial< gf_element > & $a$, const gf_poly_modulus & $F$}% 89 $g \assign a \bmod \code{$F$.modulus()}$. No restrictions on $\deg(a)$. 90\end{fcode} 91 92\begin{fcode}{void}{multiply}{polynomial< gf_element > & $g$, 93 const polynomial< gf_element > & $a$, const polynomial< gf_element > & $b$, 94 const gf_poly_modulus & $F$}% 95 $g \assign a \cdot b \bmod\code{$F$.modulus()}$. If $\deg(a)$ or $\deg(b) \geq 96 \deg(\code{$F$.modulus()})$, the \LEH is invoked. 97\end{fcode} 98 99\begin{fcode}{void}{square}{polynomial< gf_element > & $g$, 100 const polynomial< gf_element > & $a$, const gf_poly_modulus & $F$}% 101 $g \assign a^2 \bmod\code{$F$.modulus()}$. If $\deg(a) \geq \deg(\code{$F$.modulus()})$, the 102 \LEH is invoked. 103\end{fcode} 104 105\begin{fcode}{void}{power}{polynomial< gf_element > & $g$, 106 const polynomial< gf_element > & $a$, const bigint & $e$, const gf_poly_modulus & $F$}% 107 $g \assign a^e \bmod \code{$F$.modulus()}$. If $e < 0$, the \LEH is invoked. 108\end{fcode} 109 110\begin{fcode}{void}{power_x}{polynomial< gf_element > & $g$, const bigint & $e$, 111 const gf_poly_modulus & $F$}% 112 $g \assign x^e \bmod \code{$F$.modulus()}$. If $e < 0$, the \LEH is invoked. 113\end{fcode} 114 115\begin{fcode}{void}{power_x_plus_a}{polynomial< gf_element > & $g$, const bigint & $a$, 116 const bigint & $e$, const gf_poly_modulus & $F$}% 117 $g \assign (x + a)^e \bmod \code{$F$.modulus()}$. If $e < 0$, the \LEH is invoked. 118\end{fcode} 119 120 121%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 122 123\HIGH 124 125%\begin{fcode}{void}{min_poly}{polynomial< gf_element > & $h$, 126% const polynomial< gf_element > & $g$, lidia_size_t $m$, const gf_poly_modulus & $F$}% 127% computes the monic minimal polynomial $h$ of 128% ($g$ mod $F.modulus()$). 129% $m$ is an upper bound on the degree of the minimal polynomial. 130% The algorithm is probabilistic, always returns a divisor of 131% the minimal polynomial, and returns a proper divisor with 132% probability at most $m / \code{$g$.modulus()}$. 133%\end{fcode} 134% 135%\begin{fcode}{void}{checked_min_poly}{polynomial< gf_element > & $h$, 136% const polynomial< gf_element > & $g$, lidia_size_t $m$, const gf_poly_modulus & $F$}% 137% same as $min_poly$, but guarantees that result is correct. 138%\end{fcode} 139% 140%\begin{fcode}{void}{irred_poly}{polynomial< gf_element > & $h$, 141% const polynomial< gf_element > & $g$, lidia_size_t $m$, const gf_poly_modulus & $F$}% 142% same as $min_poly$, but assumes that $F.modulus()$ 143% is irreducible (or at least that the minimal polynomial of $g$ is 144% itself irreducible).\\ 145% The algorithm is deterministic (and hence is always correct). 146%\end{fcode} 147% 148%\begin{fcode}{void}{compose}{polynomial< gf_element > & $c$, 149% const polynomial< gf_element > & $g$, const polynomial< gf_element > & $h$, 150% const gf_poly_modulus & $F$}% 151% $c \assign g(h) \bmod \code{$F$.modulus()}$. 152%\end{fcode} 153 154\begin{fcode}{void}{trace_map}{polynomial< gf_element > & $w$, const polynomial< gf_element > & $a$, 155 lidia_size_t $d$, const gf_poly_modulus & $F$, const polynomial< gf_element > & $b$}% 156 $w \assign \sum_{i=0}^{d-1} a^{q^i} \bmod \code{$F$.modulus()}$. It is assumed that $d \geq 157 0$, $q$ is a power of the number of elements over which these polynomials are defined, and $b 158 \equiv x^q \lpmod\code{$F$.modulus()}\rpmod$, otherwise the behaviour of this function is 159 undefined. 160\end{fcode} 161 162 163%\begin{fcode}{void}{power_compose}{polynomial< gf_element > & $w$, const polynomial< gf_element > & $b$, lidia_size_t d, const gf_poly_modulus & $F$} 164% $w \assign x^{q^d} \bmod \code{$F$.modulus()}$.\\ 165% It is assumed that $d \geq 0$, $q$ is a power of 166% \code{$F$.modulus().modulus()}, and $b \equiv x^q \lpmod 167% \code{$F$.modulus()}\rpmod$, otherwise the behaviour of this function is 168% undefined. 169%\end{fcode} 170 171 172%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 173 174\SEEALSO 175 176\SEE{polynomial< gf_element >}, 177\SEE{poly_modulus} 178 179 180%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 181 182\EXAMPLES 183 184\begin{quote} 185\begin{verbatim} 186#include <LiDIA/polynomial.h> 187#include <LiDIA/gf_element.h> 188 189... 190 191 polynomial< gf_element > a, b, f, x, y; 192 gf_poly_modulus F; 193 194... 195 196 multiply_mod(x, a, b, f); 197 198 F.build(f); 199 multiply(y, a, b, F); 200 201 //now, x == y 202 203... 204 205\end{verbatim} 206\end{quote} 207 208 209%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 210 211\AUTHOR 212 213Victor Shoup (ideas), Thomas Pfahler 214