pb.tex

   1 \documentclass[b5paper]{book}
   2 \usepackage{hyperref}
   3 \usepackage{makeidx}
   4 \usepackage{amssymb}
   5 \usepackage{color}
   6 \usepackage{alltt}
   7 \usepackage{graphicx}
   8 \usepackage{layout}
   9 \def\union{\cup}
  10 \def\intersect{\cap}
  11 \def\getsrandom{\stackrel{\rm R}{\gets}}
  12 \def\cross{\times}
  13 \def\cat{\hspace{0.5em} \| \hspace{0.5em}}
  14 \def\catn{$\|$}
  15 \def\divides{\hspace{0.3em} | \hspace{0.3em}}
  16 \def\nequiv{\not\equiv}
  17 \def\approx{\raisebox{0.2ex}{\mbox{\small $\sim$}}}
  18 \def\lcm{{\rm lcm}}
  19 \def\gcd{{\rm gcd}}
  20 \def\log{{\rm log}}
  21 \def\ord{{\rm ord}}
  22 \def\abs{{\mathit abs}}
  23 \def\rep{{\mathit rep}}
  24 \def\mod{{\mathit\ mod\ }}
  25 \renewcommand{\pmod}[1]{\ ({\rm mod\ }{#1})}
  26 \newcommand{\floor}[1]{\left\lfloor{#1}\right\rfloor}
  27 \newcommand{\ceil}[1]{\left\lceil{#1}\right\rceil}
  28 \def\Or{{\rm\ or\ }}
  29 \def\And{{\rm\ and\ }}
  30 \def\iff{\hspace{1em}\Longleftrightarrow\hspace{1em}}
  31 \def\implies{\Rightarrow}
  32 \def\undefined{{\rm ``undefined"}}
  33 \def\Proof{\vspace{1ex}\noindent {\bf Proof:}\hspace{1em}}
  34 \let\oldphi\phi
  35 \def\phi{\varphi}
  36 \def\Pr{{\rm Pr}}
  37 \newcommand{\str}[1]{{\mathbf{#1}}}
  38 \def\F{{\mathbb F}}
  39 \def\N{{\mathbb N}}
  40 \def\Z{{\mathbb Z}}
  41 \def\R{{\mathbb R}}
  42 \def\C{{\mathbb C}}
  43 \def\Q{{\mathbb Q}}
  44 \definecolor{DGray}{gray}{0.5}
  45 \newcommand{\emailaddr}[1]{\mbox{$<${#1}$>$}}
  46 \def\twiddle{\raisebox{0.3ex}{\mbox{\tiny $\sim$}}}
  47 \def\gap{\vspace{0.5ex}}
  48 \makeindex
  49 \begin{document}
  50 \frontmatter
  51 \pagestyle{empty}
  52 \title{LibTomPoly User Manual \\ v0.04}
  53 \author{Tom St Denis \\ tomstdenis@iahu.ca}
  54 \maketitle
  55 This text and library are  hereby placed in the public domain.  This book has been
  56 formatted for B5 [176x250] paper using the \LaTeX{} {\em book} macro package.
  57
  58 \vspace{10cm}
  59
  60 \begin{flushright}Open Source.  Open Academia.  Open Minds.
  61
  62 \mbox{ }
  63
  64 Tom St Denis,
  65
  66 Ontario, Canada
  67 \end{flushright}
  68
  69 \tableofcontents
  70 \listoffigures
  71 \mainmatter
  72 \pagestyle{headings}
  73 \chapter{Introduction}
  74 \section{What is LibTomPoly?}
  75 LibTomPoly is a public domain open source library to provide polynomial basis arithmetic.  It uses the public domain
  76 library LibTomMath (not included) for the integer arithmetic and extends the functonality to provide polynomial arithmetic.
  77
  78 Technically speaking the library allows the user to perform arithmetic on elements from the group $GF(p)[x]$ and to
  79 a lesser extent (this will change in the future) over $\Z[x]$.  Essentially the math you can do with integers (including
  80 forming rings and fields) you can do with with polynomials and now you can do with LibTomPoly.
  81
  82 \section{License}
  83 LibTomPoly is public domain.  Enjoy.
  84
  85 \section{Terminology}
  86 Throughout this manual and within the library there will be some terminology that not everyone is familiar with.  It is afterall
  87 weird math.
  88
  89 \begin{figure}[here]
  90 \begin{center}
  91 \begin{small}
  92 \begin{tabular}{|l|l|}
  93 \hline \textbf{Term} & \textbf{Definition} \\
  94 \hline monic polynomial & A polynomial where the leading coefficient is a one. \\
  95 \hline irreducible polynomial & A polynomial that has no factors in a given group.  \\
  96                               & For instance, $x^2 + 4$ is irreducible in $\Z[x]$ but not \\
  97                               & in $GF(17)[x]$ since $x^2 + 4 = (x+8)(x+9) \mbox{ (mod }17\mbox{)}$.  \\
  98 \hline primitive polynomial   & An irreducible polynomial which generates all of \\
  99                               & elements of a given field (e.g. $GF(p)[x]/v(x)$) \\
 100 \hline characteristic         & An integer $k$ such that $k \cdot p(x) \equiv 0$  \\
 101 \hline deg()                  & Functon returns degree of polynomial, e.g. deg($x^6 + x^3 + 1$) = 6 \\
 102 \hline
 103 \end{tabular}
 104 \end{small}
 105 \end{center}
 106 \caption{Terminology}
 107 \end{figure}
 108
 109 \section{Building the Library}
 110 The library is not ready for production yet but you can test out the library manually if you want.  To build the library
 111 simply type
 112
 113 \begin{alltt}
 114 make
 115 \end{alltt}
 116
 117 Which will build ``libtompoly.a''.  To build a Win32 library with MSVC type
 118
 119 \begin{alltt}
 120 nmake -f makefile.msvc
 121 \end{alltt}
 122
 123 To build against this library include ``tompoly.h'' and link against ``libtompoly.a'' (or tommath.lib as appropriate).
 124 To build the included demo type
 125
 126 \begin{alltt}
 127 make demo
 128 \end{alltt}
 129
 130 Which will build ``demo'' in the current directory.  The demo is not interactive and produces results which must be manually
 131 inspected.
 132
 133 \chapter{Getting Started}
 134
 135 \section{The LibTomMath Connection}
 136 LibTomPoly is really just an extension of LibTomMath\footnote{\url{http://math.libtomcrypt.org}}.  As such the library has
 137 been designed in much the same way as far as argument passing and error handling events are concerned.  The reader is
 138 encouraged to become familiar with LibTomMath before diving into LibTomPoly.
 139
 140 \section{The pb\_poly structure}
 141 A polynomial can characterized by a few variables.  Given the C structure as follows
 142
 143 \begin{alltt}
 144 typedef struct \{
 145    int    used,                  /* number of terms */
 146           alloc;                 /* number of terms available (total) */
 147    mp_int characteristic,        /* characteristic, zero if not finite */
 148           *terms;                /* terms of polynomial */
 149 \} pb_poly;
 150 \end{alltt}
 151
 152 \begin{enumerate}
 153    \item The \textbf{used} member indicates how many terms of the \textbf{terms} array are used to represent the polynomial.
 154    \item The \textbf{alloc} member indicates the size of the \textbf{terms} array.  Also note that even if \textbf{used}
 155          is less than \textbf{alloc} the mp\_ints above \textbf{used} in the array must be set to a valid representation
 156          of zero.
 157    \item The \textbf{characteristic} member is an mp\_int representing the characteristic of the polynomial.  If the desire is to
 158          have a null characteristic (e.g. $\Z[x]$) this element must still be initialized to a valid representation
 159          of zero.
 160    \item The \textbf{terms} member is a dynamically sized array of mp\_int values which represent the coefficients for
 161          the terms of the polynomial.  They start from least to most significant degree.  E.g. $p(x) = \sum_{i=0}^{used-1} terms_i \cdot x^i$.
 162 \end{enumerate}
 163
 164 \section{Return Codes}
 165 The library uses the return codes from LibTomMath.  They are
 166
 167 \index{MP\_OKAY}\index{MP\_YES}\index{MP\_NO}\index{MP\_VAL}\index{MP\_MEM}
 168 \begin{figure}[here!]
 169 \begin{center}
 170 \begin{small}
 171 \begin{tabular}{|l|l|}
 172 \hline \textbf{Code} & \textbf{Meaning} \\
 173 \hline MP\_OKAY & The function succeeded. \\
 174 \hline MP\_VAL  & The function input was invalid. \\
 175 \hline MP\_MEM  & Heap memory exhausted. \\
 176 \hline &\\
 177 \hline MP\_YES  & Response is yes. \\
 178 \hline MP\_NO   & Response is no. \\
 179 \hline
 180 \end{tabular}
 181 \end{small}
 182 \end{center}
 183 \caption{Return Codes}
 184 \end{figure}
 185
 186 \section{Function Argument Passing}
 187 Just like LibTomMath the arguments are meant to be read left to right where the destination is on the right.  Consider
 188 the following.
 189
 190 \begin{alltt}
 191 pb_add(a, b, c);   /* c = a + b */
 192 pb_mul(a, b, c);   /* c = a * b */
 193 \end{alltt}
 194
 195 Also like LibTomMath input arguments can be specified as output arguments.  Consider.
 196
 197 \begin{alltt}
 198 pb_mul(a, b, a);   /* a = a * b */
 199 pb_gcd(a, b, b);   /* b = (a, b) */
 200 \end{alltt}
 201
 202 However, polynomial math raises another consideration.  The characteristic of the result is taken from the right most
 203 argument passed to the function.  Not all functions will return an error code if the characteristics of the inputs
 204 do not match so it's important to keep this in mind.  In general the results are undefined if not all of the polynomials
 205 have identical characteristics.
 206
 207 \section{Initializing Polynomials}
 208 In order to use a pb\_poly structure with one of the functions in this library the structure must be initialized.
 209 There are three functions provided to initialize pb\_poly structures.
 210
 211 \subsection{Default Initialization}
 212 \index{pb\_init}
 213 \begin{alltt}
 214 int pb_init(pb_poly *a, mp_int *characteristic);
 215 \end{alltt}
 216 This will initialize ``a'' with the given ``characteristic'' such that the polynomial represented is a constant zero.
 217 The mp\_int characteristic must be a valid initialized mp\_int even if a characteristic of zero is desired.  By default,
 218 the polynomial will be initialized so there are ``PB\_TERMS'' terms available.  This will grow automatically as required
 219 by the other functions.
 220
 221 \subsection{Initilization of Given Size}
 222 \index{pb\_init\_size}
 223 \begin{alltt}
 224 int pb_init_size(pb_poly *a, mp_int *characteristic, int size);
 225 \end{alltt}
 226 This behaves similar to pb\_init() except it will allocate ``size'' terms to initialize instead of ``PB\_TERMS''.  This
 227 is useful if you happen to know in advance how many terms you want.
 228
 229 \subsection{Initilization of a Copy}
 230 \index{pb\_init\_copy}
 231 \begin{alltt}
 232 int pb_init_copy(pb_poly *a, pb_poly *b);
 233 \end{alltt}
 234
 235 This will initialize ``a'' so it is a verbatim copy of ``b''.  It will copy the characteristic and all of the terms
 236 from ``b'' into ``a''.
 237
 238 \subsection{Freeing a Polynomial}
 239 \index{pb\_clear}
 240 \begin{alltt}
 241 int pb_clear(pb_poly *a);
 242 \end{alltt}
 243
 244 This will free all the memory required by ``a'' and mark it as been freed.  You can repeatedly pb\_clear() the same
 245 pb\_poly safely.
 246
 247 \chapter{Basic Operations}
 248 \section{Comparison}
 249 Comparisions with polynomials is a bit less intuitive then with integers.  Is $x^2 + 3$ greater than $x^2 + x + 4$?  To
 250 create a rational form of comparison the following comparison codes were designed.
 251
 252 \begin{figure}[here]
 253 \begin{small}
 254 \begin{center}
 255 \begin{tabular}{|l|l|}
 256 \hline \textbf{Code} & \textbf{Meaning} \\
 257 \hline PB\_EQ & The polynomials are exactly equal \\
 258 \hline PB\_DEG\_LT & The left polynomial has a lower degree than the right. \\
 259 \hline PB\_DEG\_EQ & Both have the same degree. \\
 260 \hline PB\_DEG\_GT & The left polynomial has a higher degree than the right. \\
 261 \hline
 262 \end{tabular}
 263 \end{center}
 264 \end{small}
 265 \caption{Compare Codes}
 266 \end{figure}
 267
 268 \index{pb\_cmp}
 269 \begin{alltt}
 270 int pb_cmp(pb_poly *a, pb_poly *b);
 271 \end{alltt}
 272
 273 This will compare the polynomial ``a'' to the left of the polynomial ``b''.  It will return one of the four
 274 codes listed above.  Note that the function does not compare the characteristics.  So if $a \in GF(17)[x]$ and
 275 $b \in GF(11)[x]$ were both equal to $x^2 + 3$ they would compare to PB\_EQ.  Whereas $x^3 + 4$
 276 would compare to PB\_DEG\_LT, $x^1 + 7$ would compare to $PB\_DEG\_GT$ and $x^2 + 7$ would compare to $PB\_DEG\_EQ$\footnote{If the polynomial $a$ were on the left for all three cases.}.
 277
 278 \section{Copying and Swapping}
 279 \index{pb\_copy}
 280 \begin{alltt}
 281 int pb_copy(pb_poly *src, pb_poly *dest);
 282 \end{alltt}
 283 This will copy the polynomial from ``src'' to ``dest'' verbatim.
 284
 285 \index{pb\_exch}
 286 \begin{alltt}
 287 int pb_exch(pb_poly *a, pb_poly *b);
 288 \end{alltt}
 289 This will exchange the contents of ``a'' with ``b''.
 290
 291 \section{Multiplying and Dividing by $x$}
 292 \index{pb\_lshd} \index{pb\_rshd}
 293 \begin{alltt}
 294 int pb_lshd(pb_poly *a, int i);
 295 int pb_rshd(pb_poly *a, int i);
 296 \end{alltt}
 297 These will multiply (or divide, respectfully) the polynomial ``a'' by $x^i$.  If $i \le 0$ the functions return without
 298 performing any operation.  For example,
 299
 300 \begin{alltt}
 301 pb_lshd(a, 2);  /* a(x) = a(x) * x^2 */
 302 pb_rshd(a, 7);  /* a(x) = a(x) / x^7 */
 303 \end{alltt}
 304
 305 \chapter{Basic Arithmetic}
 306 \section{Addition, Subtraction and Multiplication}
 307 \index{pb\_add} \index{pb\_sub}
 308 \begin{alltt}
 309 int pb_add(pb_poly *a, pb_poly *b, pb_poly *c);
 310 int pb_sub(pb_poly *a, pb_poly *b, pb_poly *c);
 311 int pb_mul(pb_poly *a, pb_poly *b, pb_poly *c);
 312 \end{alltt}
 313
 314 These will add (subtract or multiply, respectfully) the polynomial ``a'' and polynomial ``b'' and store the result in
 315 polynomial ``c''.  The characteristic from  ``c'' is used to calculate the result.  Note that the coefficients of ``c''
 316 will always be positive provided the characteristic of ``c'' is greater than zero.
 317
 318 Quick examples of usage.
 319
 320 \begin{alltt}
 321 pb_add(a, b, c);  /* c = a + b */
 322 pb_sub(b, a, c);  /* c = b - a */
 323 pb_mul(c, a, a);  /* a = c * a */
 324 \end{alltt}
 325
 326 \section{Division}
 327 \index{pb\_div}
 328 \begin{alltt}
 329 int pb_div(pb_poly *a, pb_poly *b, pb_poly *c, pb_poly *d);
 330 \end{alltt}
 331 This will divide the polynomial ``a'' by ``b'' and store the quotient in ``c'' and remainder in ``d''.  That is
 332
 333 \begin{equation}
 334 b(x) \cdot c(x) + d(x) = a(x)
 335 \end{equation}
 336
 337 The value of $deg(d(x))$ is always less than $deg(b(x))$.  Either of ``c'' and ``d'' can be set to \textbf{NULL} to
 338 signify their value is not desired.  This is useful if you only want the quotient or remainder but not both.
 339
 340 Since one of the destinations can be \textbf{NULL} the characteristic of the result is taken from ``b''.  The function
 341 will return an error if the characteristic of ``a'' differs from that of ``b''.
 342
 343 This function is defined for polynomials in $GF(p)[x]$ only.  A routine pb\_zdiv()\footnote{To be written!} allows the
 344 division of polynomials in $\Z[x]$.
 345
 346 \section{Modular Functions}
 347 \index{pb\_addmod} \index{pb\_submod} \index{pb\_mulmod}
 348 \begin{alltt}
 349 int pb_addmod(pb_poly *a, pb_poly *b, pb_poly *c, pb_poly *d);
 350 int pb_submod(pb_poly *a, pb_poly *b, pb_poly *c, pb_poly *d);
 351 int pb_mulmod(pb_poly *a, pb_poly *b, pb_poly *c, pb_poly *d);
 352 \end{alltt}
 353
 354 These add (subtract or multiply respectfully) the polynomial ``a'' and the polynomial ``b'' modulo the polynomial ``c''
 355 and store the result in the polynomial ``d''.
 356
 357 \chapter{Algebraic Functions}
 358
 359 \section{Monic Reductions}
 360 \index{pb\_monic}
 361 \begin{alltt}
 362 int pb_monic(pb_poly *a, pb_poly *b)
 363 \end{alltt}
 364 Makes ``b'' the monic representation of ``a'' by ensuring the most significant coefficient is one.  Only defined
 365 over $GF(p)[x]$.  Note that this is not a straight copy to ``b'' so you must ensure the characteristic of the two
 366 are equal before you call the function\footnote{Note that $a == b$ is acceptable as well.}.  Monic polynomials
 367 are related to their original polynomial through an integer $k$ as follows
 368
 369 \begin{equation}
 370 a(x) \cdot k^{-1} \equiv b(x)
 371 \end{equation}
 372
 373 \section{Extended Euclidean Algorithm}
 374 \index{pb\_exteuclid}
 375 \begin{alltt}
 376 int pb_exteuclid(pb_poly *a, pb_poly *b,
 377                  pb_poly *U1, pb_poly *U2, pb_poly *U3);
 378 \end{alltt}
 379
 380 This will compute the Euclidean algorithm and find values ``U1'', ``U2'', ``U3'' such that
 381
 382 \begin{equation}
 383 a(x) \cdot U1(x) + b(x) \cdot U2(x) = U3(x)
 384 \end{equation}
 385
 386 The value of ``U3'' is reduced to a monic polynomial.  The three destination variables are all optional and can
 387 be specified as \textbf{NULL} if they are not desired.
 388
 389 \section{Greatest Common Divisor}
 390 \index{pb\_gcd}
 391 \begin{alltt}
 392 int pb_gcd(pb_poly *a, pb_poly *b, pb_poly *c);
 393 \end{alltt}
 394 This finds the monic greatest common divisor of the two polynomials ``a'' and ``b'' and store the result in ``c''.  The
 395 operation is only defined over $GF(p)[x]$.
 396
 397 \section{Modular Inverse}
 398 \index{pb\_invmod}
 399 \begin{alltt}
 400 int pb_invmod(pb_poly *a, pb_poly *b, pb_poly *c);
 401 \end{alltt}
 402 This finds the modular inverse of ``a'' modulo ``b'' and stores the result in ``c''.  The operation is only defined over
 403 $GF(p)[x]$.  If the operation succeed then the following congruency should hold true.
 404
 405 \begin{equation}
 406 a(x)c(x) \equiv 1 \mbox{ (mod }b(x)\mbox{)}
 407 \end{equation}
 408
 409 \section{Modular Exponentiation}
 410 \index{pb\_exptmod}
 411 \begin{alltt}
 412 int pb_exptmod (pb_poly * G, mp_int * X, pb_poly * P, pb_poly * Y);
 413 \end{alltt}
 414
 415 This raise ``G'' to the power of ``X'' modulo ``P'' and stores the result in ``Y''. Or as a congruence
 416
 417 \begin{equation}
 418 Y(x) \equiv G(x)^X \mbox{ (mod }P(x)\mbox{)}
 419 \end{equation}
 420
 421 Where ``X'' can be negative\footnote{But in that case $G^{-1}(x)$ must exist modulo $P(x)$.} or positive.  This function
 422 is only defined over $GF(p)[x]$.
 423
 424 \section{Irreducibility Testing}
 425 \index{pb\_isirreduc}
 426 \begin{alltt}
 427 int pb_isirreduc(pb_poly *a, int *res);
 428 \end{alltt}
 429 Sets ``res'' to MP\_YES if ``a'' is irreducible (only for $GF(p)[x]$) otherwise sets ``res'' to MP\_NO.
 430
 431 \input{pb.ind}
 432
 433 \end{document}