pb.tex

多项式算法库,实现多项式算法,可以支持任意长度的多项式,主要用在密码学中,验证过,十分好用

the polynomial will be initialized so there are ``PB\_TERMS'' terms available.  This will grow automatically as required 
by the other functions.

\subsection{Initilization of Given Size}
\index{pb\_init\_size}
\begin{alltt}
int pb_init_size(pb_poly *a, mp_int *characteristic, int size);
\end{alltt}
This behaves similar to pb\_init() except it will allocate ``size'' terms to initialize instead of ``PB\_TERMS''.  This
is useful if you happen to know in advance how many terms you want.

\subsection{Initilization of a Copy}
\index{pb\_init\_copy}
\begin{alltt}
int pb_init_copy(pb_poly *a, pb_poly *b);
\end{alltt}

This will initialize ``a'' so it is a verbatim copy of ``b''.  It will copy the characteristic and all of the terms
from ``b'' into ``a''.

\subsection{Freeing a Polynomial}
\index{pb\_clear}
\begin{alltt}
int pb_clear(pb_poly *a);
\end{alltt}

This will free all the memory required by ``a'' and mark it as been freed.  You can repeatedly pb\_clear() the same
pb\_poly safely.

\chapter{Basic Operations}
\section{Comparison}
Comparisions with polynomials is a bit less intuitive then with integers.  Is $x^2 + 3$ greater than $x^2 + x + 4$?  To
create a rational form of comparison the following comparison codes were designed.

\begin{figure}[here]
\begin{small}
\begin{center}
\begin{tabular}{|l|l|}
\hline \textbf{Code} & \textbf{Meaning} \\
\hline PB\_EQ & The polynomials are exactly equal \\
\hline PB\_DEG\_LT & The left polynomial has a lower degree than the right. \\
\hline PB\_DEG\_EQ & Both have the same degree. \\
\hline PB\_DEG\_GT & The left polynomial has a higher degree than the right. \\
\hline
\end{tabular}
\end{center}
\end{small}
\caption{Compare Codes}
\end{figure}

\index{pb\_cmp}
\begin{alltt}
int pb_cmp(pb_poly *a, pb_poly *b);
\end{alltt}

This will compare the polynomial ``a'' to the left of the polynomial ``b''.  It will return one of the four
codes listed above.  Note that the function does not compare the characteristics.  So if $a \in GF(17)[x]$ and 
$b \in GF(11)[x]$ were both equal to $x^2 + 3$ they would compare to PB\_EQ.  Whereas $x^3 + 4$
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.}.

\section{Copying and Swapping}
\index{pb\_copy}
\begin{alltt}
int pb_copy(pb_poly *src, pb_poly *dest);
\end{alltt}
This will copy the polynomial from ``src'' to ``dest'' verbatim.

\index{pb\_exch}
\begin{alltt}
int pb_exch(pb_poly *a, pb_poly *b);
\end{alltt}
This will exchange the contents of ``a'' with ``b''.  

\section{Multiplying and Dividing by $x$}
\index{pb\_lshd} \index{pb\_rshd}
\begin{alltt}
int pb_lshd(pb_poly *a, int i);
int pb_rshd(pb_poly *a, int i);
\end{alltt}
These will multiply (or divide, respectfully) the polynomial ``a'' by $x^i$.  If $i \le 0$ the functions return without
performing any operation.  For example,

\begin{alltt}
pb_lshd(a, 2);  /* a(x) = a(x) * x^2 */
pb_rshd(a, 7);  /* a(x) = a(x) / x^7 */
\end{alltt}

\chapter{Basic Arithmetic}
\section{Addition, Subtraction and Multiplication}
\index{pb\_add} \index{pb\_sub}
\begin{alltt}
int pb_add(pb_poly *a, pb_poly *b, pb_poly *c);
int pb_sub(pb_poly *a, pb_poly *b, pb_poly *c);
int pb_mul(pb_poly *a, pb_poly *b, pb_poly *c);
\end{alltt}

These will add (subtract or multiply, respectfully) the polynomial ``a'' and polynomial ``b'' and store the result in 
polynomial ``c''.  The characteristic from  ``c'' is used to calculate the result.  Note that the coefficients of ``c'' 
will always be positive provided the characteristic of ``c'' is greater than zero.  

Quick examples of usage.

\begin{alltt}
pb_add(a, b, c);  /* c = a + b */
pb_sub(b, a, c);  /* c = b - a */
pb_mul(c, a, a);  /* a = c * a */
\end{alltt}

\section{Division}
\index{pb\_div}
\begin{alltt}
int pb_div(pb_poly *a, pb_poly *b, pb_poly *c, pb_poly *d);
\end{alltt}
This will divide the polynomial ``a'' by ``b'' and store the quotient in ``c'' and remainder in ``d''.  That is

\begin{equation}
b(x) \cdot c(x) + d(x) = a(x)
\end{equation}

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 
signify their value is not desired.  This is useful if you only want the quotient or remainder but not both.  

Since one of the destinations can be \textbf{NULL} the characteristic of the result is taken from ``b''.  The function
will return an error if the characteristic of ``a'' differs from that of ``b''.  

This function is defined for polynomials in $GF(p)[x]$ only.  A routine pb\_zdiv()\footnote{To be written!} allows the 
division of polynomials in $\Z[x]$.  

\section{Modular Functions}
\index{pb\_addmod} \index{pb\_submod} \index{pb\_mulmod}
\begin{alltt}
int pb_addmod(pb_poly *a, pb_poly *b, pb_poly *c, pb_poly *d);
int pb_submod(pb_poly *a, pb_poly *b, pb_poly *c, pb_poly *d);
int pb_mulmod(pb_poly *a, pb_poly *b, pb_poly *c, pb_poly *d);
\end{alltt}

These add (subtract or multiply respectfully) the polynomial ``a'' and the polynomial ``b'' modulo the polynomial ``c''
and store the result in the polynomial ``d''.  

\chapter{Algebraic Functions}

\section{Monic Reductions}
\index{pb\_monic}
\begin{alltt}
int pb_monic(pb_poly *a, pb_poly *b)
\end{alltt}
Makes ``b'' the monic representation of ``a'' by ensuring the most significant coefficient is one.  Only defined
over $GF(p)[x]$.  Note that this is not a straight copy to ``b'' so you must ensure the characteristic of the two
are equal before you call the function\footnote{Note that $a == b$ is acceptable as well.}.  Monic polynomials
are related to their original polynomial through an integer $k$ as follows

\begin{equation}
a(x) \cdot k^{-1} \equiv b(x)
\end{equation}

\section{Extended Euclidean Algorithm}
\index{pb\_exteuclid}
\begin{alltt}
int pb_exteuclid(pb_poly *a, pb_poly *b, 
                 pb_poly *U1, pb_poly *U2, pb_poly *U3);
\end{alltt}

This will compute the Euclidean algorithm and find values ``U1'', ``U2'', ``U3'' such that 

\begin{equation}
a(x) \cdot U1(x) + b(x) \cdot U2(x) = U3(x)
\end{equation}

The value of ``U3'' is reduced to a monic polynomial.  The three destination variables are all optional and can
be specified as \textbf{NULL} if they are not desired.

\section{Greatest Common Divisor}
\index{pb\_gcd}
\begin{alltt}
int pb_gcd(pb_poly *a, pb_poly *b, pb_poly *c);
\end{alltt}
This finds the monic greatest common divisor of the two polynomials ``a'' and ``b'' and store the result in ``c''.  The
operation is only defined over $GF(p)[x]$.  

\section{Modular Inverse}
\index{pb\_invmod}
\begin{alltt}
int pb_invmod(pb_poly *a, pb_poly *b, pb_poly *c);
\end{alltt}
This finds the modular inverse of ``a'' modulo ``b'' and stores the result in ``c''.  The operation is only defined over 
$GF(p)[x]$.  If the operation succeed then the following congruency should hold true.

\begin{equation}
a(x)c(x) \equiv 1 \mbox{ (mod }b(x)\mbox{)}
\end{equation}

\section{Modular Exponentiation}
\index{pb\_exptmod}
\begin{alltt}
int pb_exptmod (pb_poly * G, mp_int * X, pb_poly * P, pb_poly * Y);
\end{alltt}

This raise ``G'' to the power of ``X'' modulo ``P'' and stores the result in ``Y''. Or as a congruence

\begin{equation}
Y(x) \equiv G(x)^X \mbox{ (mod }P(x)\mbox{)}
\end{equation}

Where ``X'' can be negative\footnote{But in that case $G^{-1}(x)$ must exist modulo $P(x)$.} or positive.  This function
is only defined over $GF(p)[x]$.  

\section{Irreducibility Testing}
\index{pb\_isirreduc}
\begin{alltt}
int pb_isirreduc(pb_poly *a, int *res);
\end{alltt}
Sets ``res'' to MP\_YES if ``a'' is irreducible (only for $GF(p)[x]$) otherwise sets ``res'' to MP\_NO.  

\input{pb.ind}

\end{document}