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