--- Begin Message ---
Package: libtommath
Version: 0.42.0-1.1
Severity: serious
libtommath fails to build because of LaTeX errors. (Note that a new
LaTeX entered unstable recently.)
It seems you cannot use "[here]" anymore to indicate float placement;
the correct usage is "[h]", as documented e.g. here:
https://en.wikibooks.org/wiki/LaTeX/Floats,_Figures_and_Captions
I sent an email to the LaTeX maintainers asking if this change was
intentional, but let's assume it is.
Below is a patch.
Martin
> sbuild (Debian sbuild) 0.64.1 (13 Oct 2013) on m400-c2n1.hlinux.usa.hp.com
...
> /usr/bin/make manual docs DESTDIR=/«PKGBUILDDIR»/debian/tmp
> make[1]: Entering directory '/«PKGBUILDDIR»'
> echo "hello" > bn.ind
> latex bn > /dev/null
> make[1]: *** [mandvi] Error 1
--
Martin Michlmayr
Linux for HP Helion OpenStack, Hewlett-Packard
Description: LaTeX build fix
---
--- libtommath-0.42.0.orig/booker.pl 2015-06-28 00:43:10.170000000 +0000
+++ libtommath-0.42.0/booker.pl 2015-06-28 00:43:17.670000000 +0000
@@ -251,7 +251,7 @@
# FIGU,file,caption
chomp($_);
@m = split(",", $_);
- print OUT
"\\begin{center}\n\\begin{figure}[here]\n\\includegraphics{pics/$m[1]$graph}\n";
+ print OUT
"\\begin{center}\n\\begin{figure}[h]\n\\includegraphics{pics/$m[1]$graph}\n";
print OUT
"\\caption{$m[2]}\n\\label{pic:$m[1]}\n\\end{figure}\n\\end{center}\n";
$wroteline += 4;
} else {
--- libtommath-0.42.0.orig/bn.tex
+++ libtommath-0.42.0/bn.tex
@@ -257,7 +257,7 @@ the library (beat that!).
So you may be thinking ``should I use LibTomMath?'' and the answer is a
definite maybe. Let me tabulate what I think
are the pros and cons of LibTomMath by comparing it to the math routines from
GnuPG\footnote{GnuPG v1.2.3 versus LibTomMath v0.28}.
-\newpage\begin{figure}[here]
+\newpage\begin{figure}[h]
\begin{small}
\begin{center}
\begin{tabular}{|l|c|c|l|}
@@ -299,7 +299,7 @@ libtommath.a). There is no library init
There are three possible return codes a function may return.
\index{MP\_OKAY}\index{MP\_YES}\index{MP\_NO}\index{MP\_VAL}\index{MP\_MEM}
-\begin{figure}[here!]
+\begin{figure}[h!]
\begin{center}
\begin{small}
\begin{tabular}{|l|l|}
@@ -786,7 +786,7 @@ Comparisons in LibTomMath are always per
for any comparison.
\index{MP\_GT} \index{MP\_EQ} \index{MP\_LT}
-\begin{figure}[here]
+\begin{figure}[h]
\begin{center}
\begin{tabular}{|c|c|}
\hline \textbf{Result Code} & \textbf{Meaning} \\
@@ -1249,7 +1249,7 @@ make XXX
\end{alltt}
Where ``XXX'' is one of the following entries from the table \ref{fig:tuning}.
-\begin{figure}[here]
+\begin{figure}[h]
\begin{center}
\begin{small}
\begin{tabular}{|l|l|}
@@ -1681,7 +1681,7 @@ specifies the bit length of the prime de
(see fig. \ref{fig:primeopts}) which can be OR'ed together. The callback
parameters are used as in
mp\_prime\_random().
-\begin{figure}[here]
+\begin{figure}[h]
\begin{center}
\begin{small}
\begin{tabular}{|r|l|}
--- libtommath-0.42.0.orig/tommath.src
+++ libtommath-0.42.0/tommath.src
@@ -186,7 +186,7 @@ integers of significant magnitude to res
typical RSA modulus would be at least greater than $10^{309}$. However,
modern programming languages such as ISO C \cite{ISOC} and
Java \cite{JAVA} only provide instrinsic support for integers which are
relatively small and single precision.
-\begin{figure}[!here]
+\begin{figure}[!h]
\begin{center}
\begin{tabular}{|r|c|}
\hline \textbf{Data Type} & \textbf{Range} \\
@@ -377,7 +377,7 @@ the problem. However, unlike \cite{TAOC
exercises ranges from one (the easiest) to five (the hardest). The following
table sumarizes the
scoring system used.
-\begin{figure}[here]
+\begin{figure}[h]
\begin{center}
\begin{small}
\begin{tabular}{|c|l|}
@@ -584,7 +584,7 @@ any such data type but it does provide f
used within LibTomMath.
\index{mp\_int}
-\begin{figure}[here]
+\begin{figure}[h]
\begin{center}
\begin{small}
%\begin{verbatim}
@@ -681,7 +681,7 @@ will it check pointers for validity. An
\textbf{int} data type with one of the following values (fig
\ref{fig:errcodes}).
\index{MP\_OKAY} \index{MP\_VAL} \index{MP\_MEM}
-\begin{figure}[here]
+\begin{figure}[h]
\begin{center}
\begin{tabular}{|l|l|}
\hline \textbf{Value} & \textbf{Meaning} \\
@@ -730,7 +730,7 @@ An mp\_int is said to be initialized if
structure are set to valid values. The mp\_init algorithm will perform such
an action.
\index{mp\_init}
-\begin{figure}[here]
+\begin{figure}[h]
\begin{center}
\begin{tabular}{l}
\hline Algorithm \textbf{mp\_init}. \\
@@ -804,7 +804,7 @@ mp\_int structure has been properly init
When an mp\_int is no longer required by the application, the memory that has
been allocated for its digits must be
returned to the application's memory pool with the mp\_clear algorithm.
-\begin{figure}[here]
+\begin{figure}[h]
\begin{center}
\begin{tabular}{l}
\hline Algorithm \textbf{mp\_clear}. \\
@@ -868,7 +868,7 @@ result of an operation without loss of p
is large enough to simply increase the \textbf{used} digit count. However,
when the size of the array is too small it
must be re-sized appropriately to accomodate the result. The mp\_grow
algorithm will provide this functionality.
-\newpage\begin{figure}[here]
+\newpage\begin{figure}[h]
\begin{center}
\begin{tabular}{l}
\hline Algorithm \textbf{mp\_grow}. \\
@@ -922,7 +922,7 @@ Occasionally the number of digits requir
of input mp\_ints to a given algorithm. The purpose of algorithm
mp\_init\_size is similar to mp\_init except that it
will allocate \textit{at least} a specified number of digits.
-\begin{figure}[here]
+\begin{figure}[h]
\begin{small}
\begin{center}
\begin{tabular}{l}
@@ -974,7 +974,7 @@ Occasionally a function will require a s
The purpose of algorithm mp\_init\_multi is to initialize a variable length
array of mp\_int structures in a single
statement. It is essentially a shortcut to multiple initializations.
-\newpage\begin{figure}[here]
+\newpage\begin{figure}[h]
\begin{center}
\begin{tabular}{l}
\hline Algorithm \textbf{mp\_init\_multi}. \\
@@ -1033,7 +1033,7 @@ The mp\_clamp algorithm is designed to s
positive number which means that if the \textbf{used} count is decremented to
zero, the sign must be set to
\textbf{MP\_ZPOS}.
-\begin{figure}[here]
+\begin{figure}[h]
\begin{center}
\begin{tabular}{l}
\hline Algorithm \textbf{mp\_clamp}. \\
@@ -1101,7 +1101,7 @@ Assigning the value that a given mp\_int
a copy for the purposes of this text. The copy of the mp\_int will be a
separate entity that represents the same
value as the mp\_int it was copied from. The mp\_copy algorithm provides this
functionality.
-\newpage\begin{figure}[here]
+\newpage\begin{figure}[h]
\begin{center}
\begin{tabular}{l}
\hline Algorithm \textbf{mp\_copy}. \\
@@ -1216,7 +1216,7 @@ and then copy another existing mp\_int i
useful within functions that need to modify an argument but do not wish to
actually modify the original copy. The
mp\_init\_copy algorithm has been designed to help perform this task.
-\begin{figure}[here]
+\begin{figure}[h]
\begin{center}
\begin{tabular}{l}
\hline Algorithm \textbf{mp\_init\_copy}. \\
@@ -1246,7 +1246,7 @@ and \textbf{a} will be left intact.
Reseting an mp\_int to the default state is a common step in many algorithms.
The mp\_zero algorithm will be the algorithm used to
perform this task.
-\begin{figure}[here]
+\begin{figure}[h]
\begin{center}
\begin{tabular}{l}
\hline Algorithm \textbf{mp\_zero}. \\
@@ -1276,7 +1276,7 @@ After the function is completed, all of
With the mp\_int representation of an integer, calculating the absolute value
is trivial. The mp\_abs algorithm will compute
the absolute value of an mp\_int.
-\begin{figure}[here]
+\begin{figure}[h]
\begin{center}
\begin{tabular}{l}
\hline Algorithm \textbf{mp\_abs}. \\
@@ -1308,7 +1308,7 @@ This fairly trivial algorithm first elim
With the mp\_int representation of an integer, calculating the negation is
also trivial. The mp\_neg algorithm will compute
the negative of an mp\_int input.
-\begin{figure}[here]
+\begin{figure}[h]
\begin{center}
\begin{tabular}{l}
\hline Algorithm \textbf{mp\_neg}. \\
@@ -1345,7 +1345,7 @@ than the \textbf{sign} is hard--coded to
\subsection{Setting Small Constants}
Often a mp\_int must be set to a relatively small value such as $1$ or $2$.
For these cases the mp\_set algorithm is useful.
-\newpage\begin{figure}[here]
+\newpage\begin{figure}[h]
\begin{center}
\begin{tabular}{l}
\hline Algorithm \textbf{mp\_set}. \\
@@ -1386,7 +1386,7 @@ this function should take that into acco
To overcome the limitations of the mp\_set algorithm the mp\_set\_int
algorithm is ideal. It accepts a ``long''
data type as input and will always treat it as a 32-bit integer.
-\begin{figure}[here]
+\begin{figure}[h]
\begin{center}
\begin{tabular}{l}
\hline Algorithm \textbf{mp\_set\_int}. \\
@@ -1436,7 +1436,7 @@ signs are known to agree in advance.
To facilitate working with the results of the comparison functions three
constants are required.
-\begin{figure}[here]
+\begin{figure}[h]
\begin{center}
\begin{tabular}{|r|l|}
\hline \textbf{Constant} & \textbf{Meaning} \\
@@ -1449,7 +1449,7 @@ To facilitate working with the results o
\caption{Comparison Return Codes}
\end{figure}
-\begin{figure}[here]
+\begin{figure}[h]
\begin{center}
\begin{tabular}{l}
\hline Algorithm \textbf{mp\_cmp\_mag}. \\
@@ -1490,7 +1490,7 @@ smaller than $a.used$, meaning that unde
Comparing with sign considerations is also fairly critical in several routines
(\textit{division for example}). Based on an unsigned magnitude
comparison a trivial signed comparison algorithm can be written.
-\begin{figure}[here]
+\begin{figure}[h]
\begin{center}
\begin{tabular}{l}
\hline Algorithm \textbf{mp\_cmp}. \\
@@ -1571,7 +1571,7 @@ trailing digits first and propagate the
Historically that convention stems from the MPI library where ``s\_'' stood
for static functions that were hidden from the developer entirely.
\newpage
-\begin{figure}[!here]
+\begin{figure}[!h]
\begin{center}
\begin{small}
\begin{tabular}{l}
@@ -1674,7 +1674,7 @@ mp\_digit (\textit{this implies $2^{\gam
For example, the default for LibTomMath is to use a ``unsigned long'' for the
mp\_digit ``type'' while $\beta = 2^{28}$. In ISO C an ``unsigned long''
data type must be able to represent $0 \le x < 2^{32}$ meaning that in this
case $\gamma \ge 32$.
-\newpage\begin{figure}[!here]
+\newpage\begin{figure}[!h]
\begin{center}
\begin{small}
\begin{tabular}{l}
@@ -1765,7 +1765,7 @@ types.
Recall from section 5.2 that an mp\_int represents an integer with an unsigned
mantissa (\textit{the array of digits}) and a \textbf{sign}
flag. A high level addition is actually performed as a series of eight
separate cases which can be optimized down to three unique cases.
-\begin{figure}[!here]
+\begin{figure}[!h]
\begin{center}
\begin{tabular}{l}
\hline Algorithm \textbf{mp\_add}. \\
@@ -1794,7 +1794,7 @@ This algorithm performs the signed addit
either \cite{TAOCPV2} or \cite{HAC} since they both only provide unsigned
operations. The algorithm is fairly
straightforward but restricted since subtraction can only produce positive
results.
-\begin{figure}[here]
+\begin{figure}[h]
\begin{small}
\begin{center}
\begin{tabular}{|c|c|c|c|c|}
@@ -1844,7 +1844,7 @@ level functions do so. Returning their
\subsection{High Level Subtraction}
The high level signed subtraction algorithm is essentially the same as the
high level signed addition algorithm.
-\newpage\begin{figure}[!here]
+\newpage\begin{figure}[!h]
\begin{center}
\begin{tabular}{l}
\hline Algorithm \textbf{mp\_sub}. \\
@@ -1876,7 +1876,7 @@ This algorithm performs the signed subtr
\cite{HAC}. Also this algorithm is restricted by algorithm s\_mp\_sub. Chart
\ref{fig:SubChart} lists the eight possible inputs and
the operations required.
-\begin{figure}[!here]
+\begin{figure}[!h]
\begin{small}
\begin{center}
\begin{tabular}{|c|c|c|c|c|}
@@ -1922,7 +1922,7 @@ are on radix-$\beta$ digits.
In a binary system where the radix is a power of two multiplication by two not
only arises often in other algorithms it is a fairly efficient
operation to perform. A single precision logical shift left is sufficient to
multiply a single digit by two.
-\newpage\begin{figure}[!here]
+\newpage\begin{figure}[!h]
\begin{small}
\begin{center}
\begin{tabular}{l}
@@ -1978,7 +1978,7 @@ is the use of the logical shift operator
\subsection{Division by Two}
A division by two can just as easily be accomplished with a logical shift
right as multiplication by two can be with a logical shift left.
-\newpage\begin{figure}[!here]
+\newpage\begin{figure}[!h]
\begin{small}
\begin{center}
\begin{tabular}{l}
@@ -2035,7 +2035,7 @@ Given a polynomial in $x$ such as $f(x)
degree. In this case $f(x) \cdot x = a_n x^{n+1} + a_{n-1} x^n + ... + a_0
x$. From a scalar basis point of view multiplying by $x$ is equivalent to
multiplying by the integer $\beta$.
-\newpage\begin{figure}[!here]
+\newpage\begin{figure}[!h]
\begin{small}
\begin{center}
\begin{tabular}{l}
@@ -2091,7 +2091,7 @@ window of exactly $b$ digits over the in
Division by powers of $x$ is easily achieved by shifting the digits right and
removing any that will end up to the right of the zero'th digit.
-\newpage\begin{figure}[!here]
+\newpage\begin{figure}[!h]
\begin{small}
\begin{center}
\begin{tabular}{l}
@@ -2147,7 +2147,7 @@ shifts $k$ times to achieve a multiplica
\subsection{Multiplication by Power of Two}
-\newpage\begin{figure}[!here]
+\newpage\begin{figure}[!h]
\begin{small}
\begin{center}
\begin{tabular}{l}
@@ -2210,7 +2210,7 @@ chain between consecutive iterations to
\subsection{Division by Power of Two}
-\newpage\begin{figure}[!here]
+\newpage\begin{figure}[!h]
\begin{small}
\begin{center}
\begin{tabular}{l}
@@ -2263,7 +2263,7 @@ the direction of the shifts.
The last algorithm in the series of polynomial basis power of two algorithms
is calculating the remainder of division by $2^b$. This
algorithm benefits from the fact that in twos complement arithmetic $a \mbox{
(mod }2^b\mbox{)}$ is the same as $a$ AND $2^b - 1$.
-\begin{figure}[!here]
+\begin{figure}[!h]
\begin{small}
\begin{center}
\begin{tabular}{l}
@@ -2374,7 +2374,7 @@ Recall from ~GAMMA~ the definition of $\
include $\alpha$ which shall represent the number of bits in the type
\textbf{mp\_word}. This implies that $2^{\alpha} > 2 \cdot \beta^2$. The
constant $\delta = 2^{\alpha - 2lg(\beta)}$ will represent the maximal weight
of any column in a product (\textit{see ~COMBA~ for more information}).
-\newpage\begin{figure}[!here]
+\newpage\begin{figure}[!h]
\begin{small}
\begin{center}
\begin{tabular}{l}
@@ -2433,7 +2433,7 @@ innermost loop $a_{ix}$ is multiplied ag
For example, consider multiplying $576$ by $241$. That is equivalent to
computing $10^0(1)(576) + 10^1(4)(576) + 10^2(2)(576)$ which is best
visualized in the following table.
-\begin{figure}[here]
+\begin{figure}[h]
\begin{center}
\begin{tabular}{|c|c|c|c|c|c|l|}
\hline && & 5 & 7 & 6 & \\
@@ -2511,7 +2511,7 @@ the product vector $\vec x$ as follows.
Where $\vec x_n$ is the $n'th$ column of the output vector. Consider the
following example which computes the vector $\vec x$ for the multiplication
of $576$ and $241$.
-\newpage\begin{figure}[here]
+\newpage\begin{figure}[h]
\begin{small}
\begin{center}
\begin{tabular}{|c|c|c|c|c|c|}
@@ -2532,7 +2532,7 @@ At this point the vector $x = \left < 10
Now the columns must be fixed by propagating the carry upwards. The resultant
vector will have one extra dimension over the input vector which is
congruent to adding a leading zero digit.
-\begin{figure}[!here]
+\begin{figure}[!h]
\begin{small}
\begin{center}
\begin{tabular}{l}
@@ -2588,7 +2588,7 @@ The defaults for LibTomMath are $\beta =
the smaller input may not have more than $256$ digits if the Comba method is
to be used. This is quite satisfactory for most applications since
$256$ digits would allow for numbers in the range of $0 \le x < 2^{7168}$
which, is much larger than most public key cryptographic algorithms require.
-\newpage\begin{figure}[!here]
+\newpage\begin{figure}[!h]
\begin{small}
\begin{center}
\begin{tabular}{l}
@@ -2794,7 +2794,7 @@ By adding the first and last equation to
of this system of equations has made Karatsuba fairly popular. In fact the
cutoff point is often fairly low\footnote{With LibTomMath 0.18 it is 70 and 109
digits for the Intel P4 and AMD Athlon respectively.}
making it an ideal algorithm to speed up certain public key cryptosystems such
as RSA and Diffie-Hellman.
-\newpage\begin{figure}[!here]
+\newpage\begin{figure}[!h]
\begin{small}
\begin{center}
\begin{tabular}{l}
@@ -2899,7 +2899,7 @@ of two, two divisions by three and one m
the algorithm can be faster than a baseline multiplication. However, the
greater complexity of this algorithm places the cutoff point
(\textbf{TOOM\_MUL\_CUTOFF}) where Toom-Cook becomes more efficient much
higher than the Karatsuba cutoff point.
-\begin{figure}[!here]
+\begin{figure}[!h]
\begin{small}
\begin{center}
\begin{tabular}{l}
@@ -2936,7 +2936,7 @@ Continued on the next page.\\
\caption{Algorithm mp\_toom\_mul}
\end{figure}
-\newpage\begin{figure}[!here]
+\newpage\begin{figure}[!h]
\begin{small}
\begin{center}
\begin{tabular}{l}
@@ -3008,7 +3008,7 @@ straight forward.
Now that algorithms to handle multiplications of every useful dimensions have
been developed, a rather simple finishing touch is required. So far all
of the multiplication algorithms have been unsigned multiplications which
leaves only a signed multiplication algorithm to be established.
-\begin{figure}[!here]
+\begin{figure}[!h]
\begin{small}
\begin{center}
\begin{tabular}{l}
@@ -3062,7 +3062,7 @@ and $3 \cdot 1 = 1 \cdot 3$.
For any $n$-digit input, there are ${{\left (n^2 + n \right)}\over 2}$
possible unique single precision multiplications required compared to the $n^2$
required for multiplication. The following diagram gives an example of the
operations required.
-\begin{figure}[here]
+\begin{figure}[h]
\begin{center}
\begin{tabular}{ccccc|c}
&&1&2&3&\\
@@ -3091,7 +3091,7 @@ Column two of row one is a square and co
The baseline squaring algorithm is meant to be a catch-all squaring algorithm.
It will handle any of the input sizes that the faster routines
will not handle.
-\begin{figure}[!here]
+\begin{figure}[!h]
\begin{small}
\begin{center}
\begin{tabular}{l}
@@ -3170,7 +3170,7 @@ However, we cannot simply double all of
mp\_word arrays. One array will hold the squares and the other array will
hold the double products. With both arrays the doubling and
carry propagation can be moved to a $O(n)$ work level outside the $O(n^2)$
level. In this case, we have an even simpler solution in mind.
-\newpage\begin{figure}[!here]
+\newpage\begin{figure}[!h]
\begin{small}
\begin{center}
\begin{tabular}{l}
@@ -3260,7 +3260,7 @@ Consider squaring a 200 digit number wit
The 100 digit halves will not be squared using Karatsuba, but instead using
the faster Comba based squaring algorithm. If Karatsuba multiplication
were used instead, the 100 digit numbers would be squared with a slower Comba
based multiplication.
-\newpage\begin{figure}[!here]
+\newpage\begin{figure}[!h]
\begin{small}
\begin{center}
\begin{tabular}{l}
@@ -3353,7 +3353,7 @@ instead of multiplication to find the fi
derive their own Toom-Cook squaring algorithm.
\subsection{High Level Squaring}
-\newpage\begin{figure}[!here]
+\newpage\begin{figure}[!h]
\begin{small}
\begin{center}
\begin{tabular}{l}
@@ -3571,7 +3571,7 @@ With both optimizations in place the alg
is considerably faster than the straightforward $3m^2$ method.
\subsection{The Barrett Algorithm}
-\newpage\begin{figure}[!here]
+\newpage\begin{figure}[!h]
\begin{small}
\begin{center}
\begin{tabular}{l}
@@ -3645,7 +3645,7 @@ safe to do so.
In order to use algorithm mp\_reduce the value of $\mu$ must be calculated in
advance. Ideally this value should be computed once and stored for
future use so that the Barrett algorithm can be used without delay.
-\newpage\begin{figure}[!here]
+\newpage\begin{figure}[!h]
\begin{small}
\begin{center}
\begin{tabular}{l}
@@ -3691,7 +3691,7 @@ multiplication by $k^{-1}$ modulo $n$.
From these two simple facts the following simple algorithm can be derived.
-\newpage\begin{figure}[!here]
+\newpage\begin{figure}[!h]
\begin{small}
\begin{center}
\begin{tabular}{l}
@@ -3717,7 +3717,7 @@ $x$ is assumed to be initially much larg
final result of the Montgomery algorithm. If $k > lg(n)$ and $0 \le x < n^2$
then the final result is limited to
$0 \le r < \lfloor x/2^k \rfloor + n$. As a result at most a single
subtraction is required to get the residue desired.
-\begin{figure}[here]
+\begin{figure}[h]
\begin{small}
\begin{center}
\begin{tabular}{|c|l|}
@@ -3747,7 +3747,7 @@ Let $k = \lfloor lg(n) \rfloor + 1$ repr
and $k^2$ single precision additions. At this rate the algorithm is most
certainly slower than Barrett reduction and not terribly useful.
Fortunately there exists an alternative representation of the algorithm.
-\begin{figure}[!here]
+\begin{figure}[!h]
\begin{small}
\begin{center}
\begin{tabular}{l}
@@ -3769,7 +3769,7 @@ Fortunately there exists an alternative
This algorithm is equivalent since $2^tn$ is a multiple of $n$ and the lower
$k$ bits of $x$ are zero by step 2. The number of single
precision shifts has now been reduced from $2k^2$ to $k^2 + k$ which is only a
small improvement.
-\begin{figure}[here]
+\begin{figure}[h]
\begin{small}
\begin{center}
\begin{tabular}{|c|l|r|}
@@ -3802,7 +3802,7 @@ zero and the appropriate multiple of $n$
Instead of computing the reduction on a bit-by-bit basis it is actually much
faster to compute it on digit-by-digit basis. Consider the
previous algorithm re-written to compute the Montgomery reduction in this new
fashion.
-\begin{figure}[!here]
+\begin{figure}[!h]
\begin{small}
\begin{center}
\begin{tabular}{l}
@@ -3860,7 +3860,7 @@ the correct residue is $9 \cdot 15 \equi
The baseline Montgomery reduction algorithm will produce the residue for any
size input. It is designed to be a catch-all algororithm for
Montgomery reductions.
-\newpage\begin{figure}[!here]
+\newpage\begin{figure}[!h]
\begin{small}
\begin{center}
\begin{tabular}{l}
@@ -3944,7 +3944,7 @@ Perform a Comba like multiplier and insi
With this change in place the Montgomery reduction algorithm can be performed
with a Comba style multiplication loop which substantially increases
the speed of the algorithm.
-\newpage\begin{figure}[!here]
+\newpage\begin{figure}[!h]
\begin{small}
\begin{center}
\begin{tabular}{l}
@@ -4025,7 +4025,7 @@ digit, that is $\_ \hat W_{t} = \hat W_{
\subsection{Montgomery Setup}
To calculate the variable $\rho$ a relatively simple algorithm will be
required.
-\begin{figure}[!here]
+\begin{figure}[!h]
\begin{small}
\begin{center}
\begin{tabular}{l}
@@ -4081,7 +4081,7 @@ x \equiv qk + r \mbox{ (mod }(n-k)\mbox
The variable $n$ reduces modulo $n - k$ to $k$. By putting $q = \lfloor x/n
\rfloor$ and $r = x \mbox{ mod } n$
into the equation the original congruence is reproduced, thus concluding the
proof. The following algorithm is based on this observation.
-\begin{figure}[!here]
+\begin{figure}[!h]
\begin{small}
\begin{center}
\begin{tabular}{l}
@@ -4194,7 +4194,7 @@ of this algorithm has been optimized to
of $x$ and $q$. The resulting algorithm is very efficient and can lead to
substantial improvements over Barrett and Montgomery reduction when modular
exponentiations are performed.
-\newpage\begin{figure}[!here]
+\newpage\begin{figure}[!h]
\begin{small}
\begin{center}
\begin{tabular}{l}
@@ -4260,7 +4260,7 @@ does not need to be checked.
To setup the restricted Diminished Radix algorithm the value $k = \beta - n_0$
is required. This algorithm is not really complicated but provided for
completeness.
-\begin{figure}[!here]
+\begin{figure}[!h]
\begin{small}
\begin{center}
\begin{tabular}{l}
@@ -4282,7 +4282,7 @@ EXAM,bn_mp_dr_setup.c
Another algorithm which will be useful is the ability to detect a restricted
Diminished Radix modulus. An integer is said to be
of restricted Diminished Radix form if all of the digits are equal to $\beta -
1$ except the trailing digit which may be any value.
-\begin{figure}[!here]
+\begin{figure}[!h]
\begin{small}
\begin{center}
\begin{tabular}{l}
@@ -4315,7 +4315,7 @@ is a straightforward adaptation of algor
In general the restricted Diminished Radix reduction algorithm is much faster
since it has considerably lower overhead. However, this new
algorithm is much faster than either Montgomery or Barrett reduction when the
moduli are of the appropriate form.
-\begin{figure}[!here]
+\begin{figure}[!h]
\begin{small}
\begin{center}
\begin{tabular}{l}
@@ -4357,7 +4357,7 @@ positive. By using the unsigned version
\subsubsection{Unrestricted Setup}
To setup this reduction algorithm the value of $k = 2^p - n$ is required.
-\begin{figure}[!here]
+\begin{figure}[!h]
\begin{small}
\begin{center}
\begin{tabular}{l}
@@ -4396,7 +4396,7 @@ one digit than it will always be of the
that there will be value of $k$ that when added to the modulus causes a carry
in the first digit which propagates all the way to the most
significant bit. The resulting sum will be a power of two.
-\begin{figure}[!here]
+\begin{figure}[!h]
\begin{small}
\begin{center}
\begin{tabular}{l}
@@ -4498,7 +4498,7 @@ $k \over 2$ multiplications to compute t
While this current method is a considerable speed up there are further
improvements to be made. For example, the $a^{2^i}$ term does not need to
be computed in an auxilary variable. Consider the following equivalent
algorithm.
-\begin{figure}[!here]
+\begin{figure}[!h]
\begin{small}
\begin{center}
\begin{tabular}{l}
@@ -4550,7 +4550,7 @@ The first algorithm in the series of exp
to be used when a small power of an input is required (\textit{e.g. $a^5$}).
It is faster than simply multiplying $b - 1$ times for all values of
$b$ that are greater than three.
-\newpage\begin{figure}[!here]
+\newpage\begin{figure}[!h]
\begin{small}
\begin{center}
\begin{tabular}{l}
@@ -4601,7 +4601,7 @@ the $i$'th $k$-bit digit of the exponent
computes the same exponentiation. A group of $k$ bits from the exponent is
called a \textit{window}. That is it is a small window on only a
portion of the entire exponent. Consider the following modification to the
basic left to right exponentiation algorithm.
-\begin{figure}[!here]
+\begin{figure}[!h]
\begin{small}
\begin{center}
\begin{tabular}{l}
@@ -4637,7 +4637,7 @@ An optimal value of $k$ will minimize $2
approach is to brute force search amongst the values $k = 2, 3, \ldots, 8$ for
the lowest result. Table~\ref{fig:OPTK} lists optimal values of $k$
for various exponent sizes and compares the number of multiplication and
squarings required against algorithm~\ref{fig:LTOR}.
-\begin{figure}[here]
+\begin{figure}[h]
\begin{center}
\begin{small}
\begin{tabular}{|c|c|c|c|c|c|}
@@ -4666,7 +4666,7 @@ algorithm values of $g$ in the range $0
Table~\ref{fig:OPTK2} lists optimal values of $k$ for various exponent sizes
and compares the work required against algorithm~\ref{fig:KARY}.
-\begin{figure}[here]
+\begin{figure}[h]
\begin{center}
\begin{small}
\begin{tabular}{|c|c|c|c|c|c|}
@@ -4688,7 +4688,7 @@ Table~\ref{fig:OPTK2} lists optimal valu
\label{fig:OPTK2}
\end{figure}
-\newpage\begin{figure}[!here]
+\newpage\begin{figure}[!h]
\begin{small}
\begin{center}
\begin{tabular}{l}
@@ -4739,7 +4739,7 @@ will allow the exponent $b$ to be negati
value of $(1/a) \mbox{ mod }c$ is computed using the modular inverse
(\textit{see \ref{sec;modinv}}). If no inverse exists the algorithm
terminates with an error.
-\begin{figure}[!here]
+\begin{figure}[!h]
\begin{small}
\begin{center}
\begin{tabular}{l}
@@ -4791,7 +4791,7 @@ the slower s\_mp\_exptmod algorithm is u
\subsection{Barrett Modular Exponentiation}
-\newpage\begin{figure}[!here]
+\newpage\begin{figure}[!h]
\begin{small}
\begin{center}
\begin{tabular}{l}
@@ -4841,7 +4841,7 @@ Continued on next page. \\
\caption{Algorithm s\_mp\_exptmod}
\end{figure}
-\newpage\begin{figure}[!here]
+\newpage\begin{figure}[!h]
\begin{small}
\begin{center}
\begin{tabular}{l}
@@ -4955,7 +4955,7 @@ function that will be used for this modu
Calculating $b = 2^a$ can be performed much quicker than with any of the
previous algorithms. Recall that a logical shift left $m << k$ is
equivalent to $m \cdot 2^k$. By this logic when $m = 1$ a quick power of two
can be achieved.
-\begin{figure}[!here]
+\begin{figure}[!h]
\begin{small}
\begin{center}
\begin{tabular}{l}
@@ -4997,7 +4997,7 @@ the basis of this algorithm is the long-
will be used. Let $x$ represent the divisor and $y$ represent the dividend.
Let $q$ represent the integer quotient $\lfloor y / x \rfloor$ and
let $r$ represent the remainder $r = y - x \lfloor y / x \rfloor$. The
following simple algorithm will be used to start the discussion.
-\newpage\begin{figure}[!here]
+\newpage\begin{figure}[!h]
\begin{small}
\begin{center}
\begin{tabular}{l}
@@ -5093,7 +5093,7 @@ lie in the domain of a single digit. Co
At most the quotient approaches $2\beta$, however, in practice this will not
occur since that would imply the previous quotient digit was too small.
\subsection{Radix-$\beta$ Division with Remainder}
-\newpage\begin{figure}[!here]
+\newpage\begin{figure}[!h]
\begin{small}
\begin{center}
\begin{tabular}{l}
@@ -5136,7 +5136,7 @@ Continued on the next page. \\
\caption{Algorithm mp\_div}
\end{figure}
-\newpage\begin{figure}[!here]
+\newpage\begin{figure}[!h]
\begin{small}
\begin{center}
\begin{tabular}{l}
@@ -5259,7 +5259,7 @@ the helper functions assume the single d
Both addition and subtraction are performed by ``cheating'' and using mp\_set
followed by the higher level addition or subtraction
algorithms. As a result these algorithms are subtantially simpler with a
slight cost in performance.
-\newpage\begin{figure}[!here]
+\newpage\begin{figure}[!h]
\begin{small}
\begin{center}
\begin{tabular}{l}
@@ -5292,7 +5292,7 @@ Single digit multiplication arises enoug
multiplication algorithm. Essentially this algorithm is a modified version of
algorithm s\_mp\_mul\_digs where one of the multiplicands
only has one digit.
-\begin{figure}[!here]
+\begin{figure}[!h]
\begin{small}
\begin{center}
\begin{tabular}{l}
@@ -5334,7 +5334,7 @@ read from the source. This function use
Like the single digit multiplication algorithm, single digit division is also
a fairly common algorithm used in radix conversion. Since the
divisor is only a single digit a specialized variant of the division algorithm
can be used to compute the quotient.
-\newpage\begin{figure}[!here]
+\newpage\begin{figure}[!h]
\begin{small}
\begin{center}
\begin{tabular}{l}
@@ -5399,7 +5399,7 @@ simply $f'(x) = nx^{n - 1}$. Of particu
such as the real numbers. As a result the root found can be above the true
root by few and must be manually adjusted. Ideally at the end of the
algorithm the $n$'th root $b$ of an integer $a$ is desired such that $b^n \le
a$.
-\newpage\begin{figure}[!here]
+\newpage\begin{figure}[!h]
\begin{small}
\begin{center}
\begin{tabular}{l}
@@ -5452,7 +5452,7 @@ Random numbers come up in a variety of a
factoring for example, can make use of random values as starting points to
find factors of a composite integer. In this case the algorithm presented
is solely for simulations and not intended for cryptographic use.
-\newpage\begin{figure}[!here]
+\newpage\begin{figure}[!h]
\begin{small}
\begin{center}
\begin{tabular}{l}
@@ -5494,7 +5494,7 @@ map are for the common representations u
such that they are printable. While outputting as base64 may not be too
helpful for human operators it does allow communication via non binary
mediums.
-\newpage\begin{figure}[here]
+\newpage\begin{figure}[h]
\begin{center}
\begin{tabular}{cc|cc|cc|cc}
\hline \textbf{Value} & \textbf{Char} & \textbf{Value} & \textbf{Char} &
\textbf{Value} & \textbf{Char} & \textbf{Value} & \textbf{Char} \\
@@ -5522,7 +5522,7 @@ mediums.
\label{fig:ASC}
\end{figure}
-\newpage\begin{figure}[!here]
+\newpage\begin{figure}[!h]
\begin{small}
\begin{center}
\begin{tabular}{l}
@@ -5562,7 +5562,7 @@ EXAM,bn_mp_read_radix.c
\subsection{Generating Radix-$n$ Output}
Generating radix-$n$ output is fairly trivial with a division and remainder
algorithm.
-\newpage\begin{figure}[!here]
+\newpage\begin{figure}[!h]
\begin{small}
\begin{center}
\begin{tabular}{l}
@@ -5631,7 +5631,7 @@ simultaneously.
The most common approach (cite) is to reduce one input modulo another. That
is if $a$ and $b$ are divisible by some integer $k$ and if $qa + r = b$ then
$r$ is also divisible by $k$. The reduction pattern follows $\left < a , b
\right > \rightarrow \left < b, a \mbox{ mod } b \right >$.
-\newpage\begin{figure}[!here]
+\newpage\begin{figure}[!h]
\begin{small}
\begin{center}
\begin{tabular}{l}
@@ -5657,7 +5657,7 @@ relatively expensive operations to perfo
greatest common divisors. The faster approach is based on the observation
that if $k$ divides both $a$ and $b$ it will also divide $a - b$.
In particular, we would like $a - b$ to decrease in magnitude which implies
that $b \ge a$.
-\begin{figure}[!here]
+\begin{figure}[!h]
\begin{small}
\begin{center}
\begin{tabular}{l}
@@ -5691,7 +5691,7 @@ the greatest common divisor.
However, instead of factoring $b - a$ to find a suitable value of $p$ the
powers of $p$ can be removed from $a$ and $b$ that are in common first.
Then inside the loop whenever $b - a$ is divisible by some power of $p$ it can
be safely removed.
-\begin{figure}[!here]
+\begin{figure}[!h]
\begin{small}
\begin{center}
\begin{tabular}{l}
@@ -5736,7 +5736,7 @@ largest of the pair.
The algorithms presented so far cannot handle inputs which are zero or
negative. The following algorithm can handle all input cases properly
and will produce the greatest common divisor.
-\newpage\begin{figure}[!here]
+\newpage\begin{figure}[!h]
\begin{small}
\begin{center}
\begin{tabular}{l}
@@ -5823,7 +5823,7 @@ collide, that is be in synchronous state
Linear Feedback Shift Registers (LFSR) tend to use registers with periods
which are co-prime (\textit{e.g. the greatest common divisor is one.}).
Similarly in number theory if a composite $n$ has two prime factors $p$ and
$q$ then maximal order of any unit of $\Z/n\Z$ will be $[ p - 1, q - 1] $.
-\begin{figure}[!here]
+\begin{figure}[!h]
\begin{small}
\begin{center}
\begin{tabular}{l}
@@ -5946,7 +5946,7 @@ $\left ( {2 \over p } \right )^k$ equals
factors of $p$ do not have to be known. Furthermore, if $(a, p) = 1$ then the
algorithm will terminate when the recursion requests the
Jacobi symbol computation of $\left ( {1 \over a'} \right )$ which is simply
$1$.
-\newpage\begin{figure}[!here]
+\newpage\begin{figure}[!h]
\begin{small}
\begin{center}
\begin{tabular}{l}
@@ -6051,7 +6051,7 @@ binary approach is very similar to the b
equation.
\subsection{General Case}
-\newpage\begin{figure}[!here]
+\newpage\begin{figure}[!h]
\begin{small}
\begin{center}
\begin{tabular}{l}
@@ -6161,7 +6161,7 @@ be of any practical use. In the case of
approximately $80\%$ of all candidate integers. The constant
\textbf{PRIME\_SIZE} is equal to the number of primes in the test base. The
array \_\_prime\_tab is an array of the first \textbf{PRIME\_SIZE} prime
numbers.
-\begin{figure}[!here]
+\begin{figure}[!h]
\begin{small}
\begin{center}
\begin{tabular}{l}
@@ -6207,7 +6207,7 @@ of a base will divide $n - 1$ which woul
integers known as Carmichael numbers will be a pseudo-prime to all valid
bases. Fortunately such numbers are extremely rare as $n$ grows
in size.
-\begin{figure}[!here]
+\begin{figure}[!h]
\begin{small}
\begin{center}
\begin{tabular}{l}
@@ -6239,7 +6239,7 @@ candidate integers. The algorithm is b
value must be equal to $-1$. The squarings are stopped as soon as $-1$ is
observed. If the value of $1$ is observed first it means that
some value not congruent to $\pm 1$ when squared equals one which cannot occur
if $n$ is prime.
-\begin{figure}[!here]
+\begin{figure}[!h]
\begin{small}
\begin{center}
\begin{tabular}{l}
--- libtommath-0.42.0.orig/tommath.tex
+++ libtommath-0.42.0/tommath.tex
@@ -186,7 +186,7 @@ integers of significant magnitude to res
typical RSA modulus would be at least greater than $10^{309}$. However,
modern programming languages such as ISO C \cite{ISOC} and
Java \cite{JAVA} only provide instrinsic support for integers which are
relatively small and single precision.
-\begin{figure}[!here]
+\begin{figure}[!h]
\begin{center}
\begin{tabular}{|r|c|}
\hline \textbf{Data Type} & \textbf{Range} \\
@@ -377,7 +377,7 @@ the problem. However, unlike \cite{TAOC
exercises ranges from one (the easiest) to five (the hardest). The following
table sumarizes the
scoring system used.
-\begin{figure}[here]
+\begin{figure}[h]
\begin{center}
\begin{small}
\begin{tabular}{|c|l|}
@@ -545,7 +545,7 @@ mp\_exptmod() function itself and lowere
for new algorithms. This methodology allows new algorithms to be tested in a
complete framework with relative ease.
\begin{center}
-\begin{figure}[here]
+\begin{figure}[h]
\includegraphics{pics/design_process.ps}
\caption{Design Flow of the First Few Original LibTomMath Functions.}
\label{pic:design_process}
@@ -590,7 +590,7 @@ any such data type but it does provide f
used within LibTomMath.
\index{mp\_int}
-\begin{figure}[here]
+\begin{figure}[h]
\begin{center}
\begin{small}
%\begin{verbatim}
@@ -687,7 +687,7 @@ will it check pointers for validity. An
\textbf{int} data type with one of the following values (fig
\ref{fig:errcodes}).
\index{MP\_OKAY} \index{MP\_VAL} \index{MP\_MEM}
-\begin{figure}[here]
+\begin{figure}[h]
\begin{center}
\begin{tabular}{|l|l|}
\hline \textbf{Value} & \textbf{Meaning} \\
@@ -736,7 +736,7 @@ An mp\_int is said to be initialized if
structure are set to valid values. The mp\_init algorithm will perform such
an action.
\index{mp\_init}
-\begin{figure}[here]
+\begin{figure}[h]
\begin{center}
\begin{tabular}{l}
\hline Algorithm \textbf{mp\_init}. \\
@@ -815,7 +815,7 @@ mp\_int structure has been properly init
When an mp\_int is no longer required by the application, the memory that has
been allocated for its digits must be
returned to the application's memory pool with the mp\_clear algorithm.
-\begin{figure}[here]
+\begin{figure}[h]
\begin{center}
\begin{tabular}{l}
\hline Algorithm \textbf{mp\_clear}. \\
@@ -884,7 +884,7 @@ result of an operation without loss of p
is large enough to simply increase the \textbf{used} digit count. However,
when the size of the array is too small it
must be re-sized appropriately to accomodate the result. The mp\_grow
algorithm will provide this functionality.
-\newpage\begin{figure}[here]
+\newpage\begin{figure}[h]
\begin{center}
\begin{tabular}{l}
\hline Algorithm \textbf{mp\_grow}. \\
@@ -943,7 +943,7 @@ Occasionally the number of digits requir
of input mp\_ints to a given algorithm. The purpose of algorithm
mp\_init\_size is similar to mp\_init except that it
will allocate \textit{at least} a specified number of digits.
-\begin{figure}[here]
+\begin{figure}[h]
\begin{small}
\begin{center}
\begin{tabular}{l}
@@ -1000,7 +1000,7 @@ Occasionally a function will require a s
The purpose of algorithm mp\_init\_multi is to initialize a variable length
array of mp\_int structures in a single
statement. It is essentially a shortcut to multiple initializations.
-\newpage\begin{figure}[here]
+\newpage\begin{figure}[h]
\begin{center}
\begin{tabular}{l}
\hline Algorithm \textbf{mp\_init\_multi}. \\
@@ -1064,7 +1064,7 @@ The mp\_clamp algorithm is designed to s
positive number which means that if the \textbf{used} count is decremented to
zero, the sign must be set to
\textbf{MP\_ZPOS}.
-\begin{figure}[here]
+\begin{figure}[h]
\begin{center}
\begin{tabular}{l}
\hline Algorithm \textbf{mp\_clamp}. \\
@@ -1137,7 +1137,7 @@ Assigning the value that a given mp\_int
a copy for the purposes of this text. The copy of the mp\_int will be a
separate entity that represents the same
value as the mp\_int it was copied from. The mp\_copy algorithm provides this
functionality.
-\newpage\begin{figure}[here]
+\newpage\begin{figure}[h]
\begin{center}
\begin{tabular}{l}
\hline Algorithm \textbf{mp\_copy}. \\
@@ -1257,7 +1257,7 @@ and then copy another existing mp\_int i
useful within functions that need to modify an argument but do not wish to
actually modify the original copy. The
mp\_init\_copy algorithm has been designed to help perform this task.
-\begin{figure}[here]
+\begin{figure}[h]
\begin{center}
\begin{tabular}{l}
\hline Algorithm \textbf{mp\_init\_copy}. \\
@@ -1292,7 +1292,7 @@ and \textbf{a} will be left intact.
Reseting an mp\_int to the default state is a common step in many algorithms.
The mp\_zero algorithm will be the algorithm used to
perform this task.
-\begin{figure}[here]
+\begin{figure}[h]
\begin{center}
\begin{tabular}{l}
\hline Algorithm \textbf{mp\_zero}. \\
@@ -1327,7 +1327,7 @@ After the function is completed, all of
With the mp\_int representation of an integer, calculating the absolute value
is trivial. The mp\_abs algorithm will compute
the absolute value of an mp\_int.
-\begin{figure}[here]
+\begin{figure}[h]
\begin{center}
\begin{tabular}{l}
\hline Algorithm \textbf{mp\_abs}. \\
@@ -1364,7 +1364,7 @@ This fairly trivial algorithm first elim
With the mp\_int representation of an integer, calculating the negation is
also trivial. The mp\_neg algorithm will compute
the negative of an mp\_int input.
-\begin{figure}[here]
+\begin{figure}[h]
\begin{center}
\begin{tabular}{l}
\hline Algorithm \textbf{mp\_neg}. \\
@@ -1406,7 +1406,7 @@ than the \textbf{sign} is hard--coded to
\subsection{Setting Small Constants}
Often a mp\_int must be set to a relatively small value such as $1$ or $2$.
For these cases the mp\_set algorithm is useful.
-\newpage\begin{figure}[here]
+\newpage\begin{figure}[h]
\begin{center}
\begin{tabular}{l}
\hline Algorithm \textbf{mp\_set}. \\
@@ -1452,7 +1452,7 @@ this function should take that into acco
To overcome the limitations of the mp\_set algorithm the mp\_set\_int
algorithm is ideal. It accepts a ``long''
data type as input and will always treat it as a 32-bit integer.
-\begin{figure}[here]
+\begin{figure}[h]
\begin{center}
\begin{tabular}{l}
\hline Algorithm \textbf{mp\_set\_int}. \\
@@ -1507,7 +1507,7 @@ signs are known to agree in advance.
To facilitate working with the results of the comparison functions three
constants are required.
-\begin{figure}[here]
+\begin{figure}[h]
\begin{center}
\begin{tabular}{|r|l|}
\hline \textbf{Constant} & \textbf{Meaning} \\
@@ -1520,7 +1520,7 @@ To facilitate working with the results o
\caption{Comparison Return Codes}
\end{figure}
-\begin{figure}[here]
+\begin{figure}[h]
\begin{center}
\begin{tabular}{l}
\hline Algorithm \textbf{mp\_cmp\_mag}. \\
@@ -1566,7 +1566,7 @@ smaller than $a.used$, meaning that unde
Comparing with sign considerations is also fairly critical in several routines
(\textit{division for example}). Based on an unsigned magnitude
comparison a trivial signed comparison algorithm can be written.
-\begin{figure}[here]
+\begin{figure}[h]
\begin{center}
\begin{tabular}{l}
\hline Algorithm \textbf{mp\_cmp}. \\
@@ -1651,7 +1651,7 @@ trailing digits first and propagate the
Historically that convention stems from the MPI library where ``s\_'' stood
for static functions that were hidden from the developer entirely.
\newpage
-\begin{figure}[!here]
+\begin{figure}[!h]
\begin{center}
\begin{small}
\begin{tabular}{l}
@@ -1758,7 +1758,7 @@ mp\_digit (\textit{this implies $2^{\gam
For example, the default for LibTomMath is to use a ``unsigned long'' for the
mp\_digit ``type'' while $\beta = 2^{28}$. In ISO C an ``unsigned long''
data type must be able to represent $0 \le x < 2^{32}$ meaning that in this
case $\gamma \ge 32$.
-\newpage\begin{figure}[!here]
+\newpage\begin{figure}[!h]
\begin{center}
\begin{small}
\begin{tabular}{l}
@@ -1854,7 +1854,7 @@ types.
Recall from section 5.2 that an mp\_int represents an integer with an unsigned
mantissa (\textit{the array of digits}) and a \textbf{sign}
flag. A high level addition is actually performed as a series of eight
separate cases which can be optimized down to three unique cases.
-\begin{figure}[!here]
+\begin{figure}[!h]
\begin{center}
\begin{tabular}{l}
\hline Algorithm \textbf{mp\_add}. \\
@@ -1883,7 +1883,7 @@ This algorithm performs the signed addit
either \cite{TAOCPV2} or \cite{HAC} since they both only provide unsigned
operations. The algorithm is fairly
straightforward but restricted since subtraction can only produce positive
results.
-\begin{figure}[here]
+\begin{figure}[h]
\begin{small}
\begin{center}
\begin{tabular}{|c|c|c|c|c|}
@@ -1938,7 +1938,7 @@ level functions do so. Returning their
\subsection{High Level Subtraction}
The high level signed subtraction algorithm is essentially the same as the
high level signed addition algorithm.
-\newpage\begin{figure}[!here]
+\newpage\begin{figure}[!h]
\begin{center}
\begin{tabular}{l}
\hline Algorithm \textbf{mp\_sub}. \\
@@ -1970,7 +1970,7 @@ This algorithm performs the signed subtr
\cite{HAC}. Also this algorithm is restricted by algorithm s\_mp\_sub. Chart
\ref{fig:SubChart} lists the eight possible inputs and
the operations required.
-\begin{figure}[!here]
+\begin{figure}[!h]
\begin{small}
\begin{center}
\begin{tabular}{|c|c|c|c|c|}
@@ -2020,7 +2020,7 @@ are on radix-$\beta$ digits.
In a binary system where the radix is a power of two multiplication by two not
only arises often in other algorithms it is a fairly efficient
operation to perform. A single precision logical shift left is sufficient to
multiply a single digit by two.
-\newpage\begin{figure}[!here]
+\newpage\begin{figure}[!h]
\begin{small}
\begin{center}
\begin{tabular}{l}
@@ -2081,7 +2081,7 @@ is the use of the logical shift operator
\subsection{Division by Two}
A division by two can just as easily be accomplished with a logical shift
right as multiplication by two can be with a logical shift left.
-\newpage\begin{figure}[!here]
+\newpage\begin{figure}[!h]
\begin{small}
\begin{center}
\begin{tabular}{l}
@@ -2143,7 +2143,7 @@ Given a polynomial in $x$ such as $f(x)
degree. In this case $f(x) \cdot x = a_n x^{n+1} + a_{n-1} x^n + ... + a_0
x$. From a scalar basis point of view multiplying by $x$ is equivalent to
multiplying by the integer $\beta$.
-\newpage\begin{figure}[!here]
+\newpage\begin{figure}[!h]
\begin{small}
\begin{center}
\begin{tabular}{l}
@@ -2186,7 +2186,7 @@ step 8 sets the lower $b$ digits to zero
\newpage
\begin{center}
-\begin{figure}[here]
+\begin{figure}[h]
\includegraphics{pics/sliding_window.ps}
\caption{Sliding Window Movement}
\label{pic:sliding_window}
@@ -2210,7 +2210,7 @@ window of exactly $b$ digits over the in
Division by powers of $x$ is easily achieved by shifting the digits right and
removing any that will end up to the right of the zero'th digit.
-\newpage\begin{figure}[!here]
+\newpage\begin{figure}[!h]
\begin{small}
\begin{center}
\begin{tabular}{l}
@@ -2271,7 +2271,7 @@ shifts $k$ times to achieve a multiplica
\subsection{Multiplication by Power of Two}
-\newpage\begin{figure}[!here]
+\newpage\begin{figure}[!h]
\begin{small}
\begin{center}
\begin{tabular}{l}
@@ -2339,7 +2339,7 @@ chain between consecutive iterations to
\subsection{Division by Power of Two}
-\newpage\begin{figure}[!here]
+\newpage\begin{figure}[!h]
\begin{small}
\begin{center}
\begin{tabular}{l}
@@ -2397,7 +2397,7 @@ the direction of the shifts.
The last algorithm in the series of polynomial basis power of two algorithms
is calculating the remainder of division by $2^b$. This
algorithm benefits from the fact that in twos complement arithmetic $a \mbox{
(mod }2^b\mbox{)}$ is the same as $a$ AND $2^b - 1$.
-\begin{figure}[!here]
+\begin{figure}[!h]
\begin{small}
\begin{center}
\begin{tabular}{l}
@@ -2513,7 +2513,7 @@ Recall from sub-section 4.2.2 the defini
include $\alpha$ which shall represent the number of bits in the type
\textbf{mp\_word}. This implies that $2^{\alpha} > 2 \cdot \beta^2$. The
constant $\delta = 2^{\alpha - 2lg(\beta)}$ will represent the maximal weight
of any column in a product (\textit{see sub-section 5.2.2 for more
information}).
-\newpage\begin{figure}[!here]
+\newpage\begin{figure}[!h]
\begin{small}
\begin{center}
\begin{tabular}{l}
@@ -2572,7 +2572,7 @@ innermost loop $a_{ix}$ is multiplied ag
For example, consider multiplying $576$ by $241$. That is equivalent to
computing $10^0(1)(576) + 10^1(4)(576) + 10^2(2)(576)$ which is best
visualized in the following table.
-\begin{figure}[here]
+\begin{figure}[h]
\begin{center}
\begin{tabular}{|c|c|c|c|c|c|l|}
\hline && & 5 & 7 & 6 & \\
@@ -2654,7 +2654,7 @@ the product vector $\vec x$ as follows.
Where $\vec x_n$ is the $n'th$ column of the output vector. Consider the
following example which computes the vector $\vec x$ for the multiplication
of $576$ and $241$.
-\newpage\begin{figure}[here]
+\newpage\begin{figure}[h]
\begin{small}
\begin{center}
\begin{tabular}{|c|c|c|c|c|c|}
@@ -2675,7 +2675,7 @@ At this point the vector $x = \left < 10
Now the columns must be fixed by propagating the carry upwards. The resultant
vector will have one extra dimension over the input vector which is
congruent to adding a leading zero digit.
-\begin{figure}[!here]
+\begin{figure}[!h]
\begin{small}
\begin{center}
\begin{tabular}{l}
@@ -2731,7 +2731,7 @@ The defaults for LibTomMath are $\beta =
the smaller input may not have more than $256$ digits if the Comba method is
to be used. This is quite satisfactory for most applications since
$256$ digits would allow for numbers in the range of $0 \le x < 2^{7168}$
which, is much larger than most public key cryptographic algorithms require.
-\newpage\begin{figure}[!here]
+\newpage\begin{figure}[!h]
\begin{small}
\begin{center}
\begin{tabular}{l}
@@ -2942,7 +2942,7 @@ By adding the first and last equation to
of this system of equations has made Karatsuba fairly popular. In fact the
cutoff point is often fairly low\footnote{With LibTomMath 0.18 it is 70 and 109
digits for the Intel P4 and AMD Athlon respectively.}
making it an ideal algorithm to speed up certain public key cryptosystems such
as RSA and Diffie-Hellman.
-\newpage\begin{figure}[!here]
+\newpage\begin{figure}[!h]
\begin{small}
\begin{center}
\begin{tabular}{l}
@@ -3052,7 +3052,7 @@ of two, two divisions by three and one m
the algorithm can be faster than a baseline multiplication. However, the
greater complexity of this algorithm places the cutoff point
(\textbf{TOOM\_MUL\_CUTOFF}) where Toom-Cook becomes more efficient much
higher than the Karatsuba cutoff point.
-\begin{figure}[!here]
+\begin{figure}[!h]
\begin{small}
\begin{center}
\begin{tabular}{l}
@@ -3089,7 +3089,7 @@ Continued on the next page.\\
\caption{Algorithm mp\_toom\_mul}
\end{figure}
-\newpage\begin{figure}[!here]
+\newpage\begin{figure}[!h]
\begin{small}
\begin{center}
\begin{tabular}{l}
@@ -3166,7 +3166,7 @@ straight forward.
Now that algorithms to handle multiplications of every useful dimensions have
been developed, a rather simple finishing touch is required. So far all
of the multiplication algorithms have been unsigned multiplications which
leaves only a signed multiplication algorithm to be established.
-\begin{figure}[!here]
+\begin{figure}[!h]
\begin{small}
\begin{center}
\begin{tabular}{l}
@@ -3225,7 +3225,7 @@ and $3 \cdot 1 = 1 \cdot 3$.
For any $n$-digit input, there are ${{\left (n^2 + n \right)}\over 2}$
possible unique single precision multiplications required compared to the $n^2$
required for multiplication. The following diagram gives an example of the
operations required.
-\begin{figure}[here]
+\begin{figure}[h]
\begin{center}
\begin{tabular}{ccccc|c}
&&1&2&3&\\
@@ -3253,7 +3253,7 @@ Column two of row one is a square and co
The baseline squaring algorithm is meant to be a catch-all squaring algorithm.
It will handle any of the input sizes that the faster routines
will not handle.
-\begin{figure}[!here]
+\begin{figure}[!h]
\begin{small}
\begin{center}
\begin{tabular}{l}
@@ -3337,7 +3337,7 @@ However, we cannot simply double all of
mp\_word arrays. One array will hold the squares and the other array will
hold the double products. With both arrays the doubling and
carry propagation can be moved to a $O(n)$ work level outside the $O(n^2)$
level. In this case, we have an even simpler solution in mind.
-\newpage\begin{figure}[!here]
+\newpage\begin{figure}[!h]
\begin{small}
\begin{center}
\begin{tabular}{l}
@@ -3432,7 +3432,7 @@ Consider squaring a 200 digit number wit
The 100 digit halves will not be squared using Karatsuba, but instead using
the faster Comba based squaring algorithm. If Karatsuba multiplication
were used instead, the 100 digit numbers would be squared with a slower Comba
based multiplication.
-\newpage\begin{figure}[!here]
+\newpage\begin{figure}[!h]
\begin{small}
\begin{center}
\begin{tabular}{l}
@@ -3530,7 +3530,7 @@ instead of multiplication to find the fi
derive their own Toom-Cook squaring algorithm.
\subsection{High Level Squaring}
-\newpage\begin{figure}[!here]
+\newpage\begin{figure}[!h]
\begin{small}
\begin{center}
\begin{tabular}{l}
@@ -3752,7 +3752,7 @@ With both optimizations in place the alg
is considerably faster than the straightforward $3m^2$ method.
\subsection{The Barrett Algorithm}
-\newpage\begin{figure}[!here]
+\newpage\begin{figure}[!h]
\begin{small}
\begin{center}
\begin{tabular}{l}
@@ -3831,7 +3831,7 @@ safe to do so.
In order to use algorithm mp\_reduce the value of $\mu$ must be calculated in
advance. Ideally this value should be computed once and stored for
future use so that the Barrett algorithm can be used without delay.
-\newpage\begin{figure}[!here]
+\newpage\begin{figure}[!h]
\begin{small}
\begin{center}
\begin{tabular}{l}
@@ -3882,7 +3882,7 @@ multiplication by $k^{-1}$ modulo $n$.
From these two simple facts the following simple algorithm can be derived.
-\newpage\begin{figure}[!here]
+\newpage\begin{figure}[!h]
\begin{small}
\begin{center}
\begin{tabular}{l}
@@ -3908,7 +3908,7 @@ $x$ is assumed to be initially much larg
final result of the Montgomery algorithm. If $k > lg(n)$ and $0 \le x < n^2$
then the final result is limited to
$0 \le r < \lfloor x/2^k \rfloor + n$. As a result at most a single
subtraction is required to get the residue desired.
-\begin{figure}[here]
+\begin{figure}[h]
\begin{small}
\begin{center}
\begin{tabular}{|c|l|}
@@ -3938,7 +3938,7 @@ Let $k = \lfloor lg(n) \rfloor + 1$ repr
and $k^2$ single precision additions. At this rate the algorithm is most
certainly slower than Barrett reduction and not terribly useful.
Fortunately there exists an alternative representation of the algorithm.
-\begin{figure}[!here]
+\begin{figure}[!h]
\begin{small}
\begin{center}
\begin{tabular}{l}
@@ -3960,7 +3960,7 @@ Fortunately there exists an alternative
This algorithm is equivalent since $2^tn$ is a multiple of $n$ and the lower
$k$ bits of $x$ are zero by step 2. The number of single
precision shifts has now been reduced from $2k^2$ to $k^2 + k$ which is only a
small improvement.
-\begin{figure}[here]
+\begin{figure}[h]
\begin{small}
\begin{center}
\begin{tabular}{|c|l|r|}
@@ -3993,7 +3993,7 @@ zero and the appropriate multiple of $n$
Instead of computing the reduction on a bit-by-bit basis it is actually much
faster to compute it on digit-by-digit basis. Consider the
previous algorithm re-written to compute the Montgomery reduction in this new
fashion.
-\begin{figure}[!here]
+\begin{figure}[!h]
\begin{small}
\begin{center}
\begin{tabular}{l}
@@ -4051,7 +4051,7 @@ the correct residue is $9 \cdot 15 \equi
The baseline Montgomery reduction algorithm will produce the residue for any
size input. It is designed to be a catch-all algororithm for
Montgomery reductions.
-\newpage\begin{figure}[!here]
+\newpage\begin{figure}[!h]
\begin{small}
\begin{center}
\begin{tabular}{l}
@@ -4139,7 +4139,7 @@ Perform a Comba like multiplier and insi
With this change in place the Montgomery reduction algorithm can be performed
with a Comba style multiplication loop which substantially increases
the speed of the algorithm.
-\newpage\begin{figure}[!here]
+\newpage\begin{figure}[!h]
\begin{small}
\begin{center}
\begin{tabular}{l}
@@ -4225,7 +4225,7 @@ digit, that is $\_ \hat W_{t} = \hat W_{
\subsection{Montgomery Setup}
To calculate the variable $\rho$ a relatively simple algorithm will be
required.
-\begin{figure}[!here]
+\begin{figure}[!h]
\begin{small}
\begin{center}
\begin{tabular}{l}
@@ -4286,7 +4286,7 @@ x \equiv qk + r \mbox{ (mod }(n-k)\mbox
The variable $n$ reduces modulo $n - k$ to $k$. By putting $q = \lfloor x/n
\rfloor$ and $r = x \mbox{ mod } n$
into the equation the original congruence is reproduced, thus concluding the
proof. The following algorithm is based on this observation.
-\begin{figure}[!here]
+\begin{figure}[!h]
\begin{small}
\begin{center}
\begin{tabular}{l}
@@ -4399,7 +4399,7 @@ of this algorithm has been optimized to
of $x$ and $q$. The resulting algorithm is very efficient and can lead to
substantial improvements over Barrett and Montgomery reduction when modular
exponentiations are performed.
-\newpage\begin{figure}[!here]
+\newpage\begin{figure}[!h]
\begin{small}
\begin{center}
\begin{tabular}{l}
@@ -4470,7 +4470,7 @@ does not need to be checked.
To setup the restricted Diminished Radix algorithm the value $k = \beta - n_0$
is required. This algorithm is not really complicated but provided for
completeness.
-\begin{figure}[!here]
+\begin{figure}[!h]
\begin{small}
\begin{center}
\begin{tabular}{l}
@@ -4497,7 +4497,7 @@ completeness.
Another algorithm which will be useful is the ability to detect a restricted
Diminished Radix modulus. An integer is said to be
of restricted Diminished Radix form if all of the digits are equal to $\beta -
1$ except the trailing digit which may be any value.
-\begin{figure}[!here]
+\begin{figure}[!h]
\begin{small}
\begin{center}
\begin{tabular}{l}
@@ -4535,7 +4535,7 @@ is a straightforward adaptation of algor
In general the restricted Diminished Radix reduction algorithm is much faster
since it has considerably lower overhead. However, this new
algorithm is much faster than either Montgomery or Barrett reduction when the
moduli are of the appropriate form.
-\begin{figure}[!here]
+\begin{figure}[!h]
\begin{small}
\begin{center}
\begin{tabular}{l}
@@ -4582,7 +4582,7 @@ positive. By using the unsigned version
\subsubsection{Unrestricted Setup}
To setup this reduction algorithm the value of $k = 2^p - n$ is required.
-\begin{figure}[!here]
+\begin{figure}[!h]
\begin{small}
\begin{center}
\begin{tabular}{l}
@@ -4626,7 +4626,7 @@ one digit than it will always be of the
that there will be value of $k$ that when added to the modulus causes a carry
in the first digit which propagates all the way to the most
significant bit. The resulting sum will be a power of two.
-\begin{figure}[!here]
+\begin{figure}[!h]
\begin{small}
\begin{center}
\begin{tabular}{l}
@@ -4733,7 +4733,7 @@ $k \over 2$ multiplications to compute t
While this current method is a considerable speed up there are further
improvements to be made. For example, the $a^{2^i}$ term does not need to
be computed in an auxilary variable. Consider the following equivalent
algorithm.
-\begin{figure}[!here]
+\begin{figure}[!h]
\begin{small}
\begin{center}
\begin{tabular}{l}
@@ -4785,7 +4785,7 @@ The first algorithm in the series of exp
to be used when a small power of an input is required (\textit{e.g. $a^5$}).
It is faster than simply multiplying $b - 1$ times for all values of
$b$ that are greater than three.
-\newpage\begin{figure}[!here]
+\newpage\begin{figure}[!h]
\begin{small}
\begin{center}
\begin{tabular}{l}
@@ -4841,7 +4841,7 @@ the $i$'th $k$-bit digit of the exponent
computes the same exponentiation. A group of $k$ bits from the exponent is
called a \textit{window}. That is it is a small window on only a
portion of the entire exponent. Consider the following modification to the
basic left to right exponentiation algorithm.
-\begin{figure}[!here]
+\begin{figure}[!h]
\begin{small}
\begin{center}
\begin{tabular}{l}
@@ -4877,7 +4877,7 @@ An optimal value of $k$ will minimize $2
approach is to brute force search amongst the values $k = 2, 3, \ldots, 8$ for
the lowest result. Table~\ref{fig:OPTK} lists optimal values of $k$
for various exponent sizes and compares the number of multiplication and
squarings required against algorithm~\ref{fig:LTOR}.
-\begin{figure}[here]
+\begin{figure}[h]
\begin{center}
\begin{small}
\begin{tabular}{|c|c|c|c|c|c|}
@@ -4906,7 +4906,7 @@ algorithm values of $g$ in the range $0
Table~\ref{fig:OPTK2} lists optimal values of $k$ for various exponent sizes
and compares the work required against algorithm~\ref{fig:KARY}.
-\begin{figure}[here]
+\begin{figure}[h]
\begin{center}
\begin{small}
\begin{tabular}{|c|c|c|c|c|c|}
@@ -4928,7 +4928,7 @@ Table~\ref{fig:OPTK2} lists optimal valu
\label{fig:OPTK2}
\end{figure}
-\newpage\begin{figure}[!here]
+\newpage\begin{figure}[!h]
\begin{small}
\begin{center}
\begin{tabular}{l}
@@ -4979,7 +4979,7 @@ will allow the exponent $b$ to be negati
value of $(1/a) \mbox{ mod }c$ is computed using the modular inverse
(\textit{see \ref{sec;modinv}}). If no inverse exists the algorithm
terminates with an error.
-\begin{figure}[!here]
+\begin{figure}[!h]
\begin{small}
\begin{center}
\begin{tabular}{l}
@@ -5036,7 +5036,7 @@ the slower s\_mp\_exptmod algorithm is u
\subsection{Barrett Modular Exponentiation}
-\newpage\begin{figure}[!here]
+\newpage\begin{figure}[!h]
\begin{small}
\begin{center}
\begin{tabular}{l}
@@ -5086,7 +5086,7 @@ Continued on next page. \\
\caption{Algorithm s\_mp\_exptmod}
\end{figure}
-\newpage\begin{figure}[!here]
+\newpage\begin{figure}[!h]
\begin{small}
\begin{center}
\begin{tabular}{l}
@@ -5178,7 +5178,7 @@ algorithm from having to perform trivial
the two cases of $mode = 1$ and $mode = 2$ respectively.
\begin{center}
-\begin{figure}[here]
+\begin{figure}[h]
\includegraphics{pics/expt_state.ps}
\caption{Sliding Window State Diagram}
\label{pic:expt_state}
@@ -5211,7 +5211,7 @@ function that will be used for this modu
Calculating $b = 2^a$ can be performed much quicker than with any of the
previous algorithms. Recall that a logical shift left $m << k$ is
equivalent to $m \cdot 2^k$. By this logic when $m = 1$ a quick power of two
can be achieved.
-\begin{figure}[!here]
+\begin{figure}[!h]
\begin{small}
\begin{center}
\begin{tabular}{l}
@@ -5258,7 +5258,7 @@ the basis of this algorithm is the long-
will be used. Let $x$ represent the divisor and $y$ represent the dividend.
Let $q$ represent the integer quotient $\lfloor y / x \rfloor$ and
let $r$ represent the remainder $r = y - x \lfloor y / x \rfloor$. The
following simple algorithm will be used to start the discussion.
-\newpage\begin{figure}[!here]
+\newpage\begin{figure}[!h]
\begin{small}
\begin{center}
\begin{tabular}{l}
@@ -5354,7 +5354,7 @@ lie in the domain of a single digit. Co
At most the quotient approaches $2\beta$, however, in practice this will not
occur since that would imply the previous quotient digit was too small.
\subsection{Radix-$\beta$ Division with Remainder}
-\newpage\begin{figure}[!here]
+\newpage\begin{figure}[!h]
\begin{small}
\begin{center}
\begin{tabular}{l}
@@ -5397,7 +5397,7 @@ Continued on the next page. \\
\caption{Algorithm mp\_div}
\end{figure}
-\newpage\begin{figure}[!here]
+\newpage\begin{figure}[!h]
\begin{small}
\begin{center}
\begin{tabular}{l}
@@ -5525,7 +5525,7 @@ the helper functions assume the single d
Both addition and subtraction are performed by ``cheating'' and using mp\_set
followed by the higher level addition or subtraction
algorithms. As a result these algorithms are subtantially simpler with a
slight cost in performance.
-\newpage\begin{figure}[!here]
+\newpage\begin{figure}[!h]
\begin{small}
\begin{center}
\begin{tabular}{l}
@@ -5563,7 +5563,7 @@ Single digit multiplication arises enoug
multiplication algorithm. Essentially this algorithm is a modified version of
algorithm s\_mp\_mul\_digs where one of the multiplicands
only has one digit.
-\begin{figure}[!here]
+\begin{figure}[!h]
\begin{small}
\begin{center}
\begin{tabular}{l}
@@ -5610,7 +5610,7 @@ read from the source. This function use
Like the single digit multiplication algorithm, single digit division is also
a fairly common algorithm used in radix conversion. Since the
divisor is only a single digit a specialized variant of the division algorithm
can be used to compute the quotient.
-\newpage\begin{figure}[!here]
+\newpage\begin{figure}[!h]
\begin{small}
\begin{center}
\begin{tabular}{l}
@@ -5680,7 +5680,7 @@ simply $f'(x) = nx^{n - 1}$. Of particu
such as the real numbers. As a result the root found can be above the true
root by few and must be manually adjusted. Ideally at the end of the
algorithm the $n$'th root $b$ of an integer $a$ is desired such that $b^n \le
a$.
-\newpage\begin{figure}[!here]
+\newpage\begin{figure}[!h]
\begin{small}
\begin{center}
\begin{tabular}{l}
@@ -5738,7 +5738,7 @@ Random numbers come up in a variety of a
factoring for example, can make use of random values as starting points to
find factors of a composite integer. In this case the algorithm presented
is solely for simulations and not intended for cryptographic use.
-\newpage\begin{figure}[!here]
+\newpage\begin{figure}[!h]
\begin{small}
\begin{center}
\begin{tabular}{l}
@@ -5785,7 +5785,7 @@ map are for the common representations u
such that they are printable. While outputting as base64 may not be too
helpful for human operators it does allow communication via non binary
mediums.
-\newpage\begin{figure}[here]
+\newpage\begin{figure}[h]
\begin{center}
\begin{tabular}{cc|cc|cc|cc}
\hline \textbf{Value} & \textbf{Char} & \textbf{Value} & \textbf{Char} &
\textbf{Value} & \textbf{Char} & \textbf{Value} & \textbf{Char} \\
@@ -5813,7 +5813,7 @@ mediums.
\label{fig:ASC}
\end{figure}
-\newpage\begin{figure}[!here]
+\newpage\begin{figure}[!h]
\begin{small}
\begin{center}
\begin{tabular}{l}
@@ -5858,7 +5858,7 @@ as part of larger input without any sign
\subsection{Generating Radix-$n$ Output}
Generating radix-$n$ output is fairly trivial with a division and remainder
algorithm.
-\newpage\begin{figure}[!here]
+\newpage\begin{figure}[!h]
\begin{small}
\begin{center}
\begin{tabular}{l}
@@ -5932,7 +5932,7 @@ simultaneously.
The most common approach (cite) is to reduce one input modulo another. That
is if $a$ and $b$ are divisible by some integer $k$ and if $qa + r = b$ then
$r$ is also divisible by $k$. The reduction pattern follows $\left < a , b
\right > \rightarrow \left < b, a \mbox{ mod } b \right >$.
-\newpage\begin{figure}[!here]
+\newpage\begin{figure}[!h]
\begin{small}
\begin{center}
\begin{tabular}{l}
@@ -5958,7 +5958,7 @@ relatively expensive operations to perfo
greatest common divisors. The faster approach is based on the observation
that if $k$ divides both $a$ and $b$ it will also divide $a - b$.
In particular, we would like $a - b$ to decrease in magnitude which implies
that $b \ge a$.
-\begin{figure}[!here]
+\begin{figure}[!h]
\begin{small}
\begin{center}
\begin{tabular}{l}
@@ -5992,7 +5992,7 @@ the greatest common divisor.
However, instead of factoring $b - a$ to find a suitable value of $p$ the
powers of $p$ can be removed from $a$ and $b$ that are in common first.
Then inside the loop whenever $b - a$ is divisible by some power of $p$ it can
be safely removed.
-\begin{figure}[!here]
+\begin{figure}[!h]
\begin{small}
\begin{center}
\begin{tabular}{l}
@@ -6037,7 +6037,7 @@ largest of the pair.
The algorithms presented so far cannot handle inputs which are zero or
negative. The following algorithm can handle all input cases properly
and will produce the greatest common divisor.
-\newpage\begin{figure}[!here]
+\newpage\begin{figure}[!h]
\begin{small}
\begin{center}
\begin{tabular}{l}
@@ -6129,7 +6129,7 @@ collide, that is be in synchronous state
Linear Feedback Shift Registers (LFSR) tend to use registers with periods
which are co-prime (\textit{e.g. the greatest common divisor is one.}).
Similarly in number theory if a composite $n$ has two prime factors $p$ and
$q$ then maximal order of any unit of $\Z/n\Z$ will be $[ p - 1, q - 1] $.
-\begin{figure}[!here]
+\begin{figure}[!h]
\begin{small}
\begin{center}
\begin{tabular}{l}
@@ -6257,7 +6257,7 @@ $\left ( {2 \over p } \right )^k$ equals
factors of $p$ do not have to be known. Furthermore, if $(a, p) = 1$ then the
algorithm will terminate when the recursion requests the
Jacobi symbol computation of $\left ( {1 \over a'} \right )$ which is simply
$1$.
-\newpage\begin{figure}[!here]
+\newpage\begin{figure}[!h]
\begin{small}
\begin{center}
\begin{tabular}{l}
@@ -6367,7 +6367,7 @@ binary approach is very similar to the b
equation.
\subsection{General Case}
-\newpage\begin{figure}[!here]
+\newpage\begin{figure}[!h]
\begin{small}
\begin{center}
\begin{tabular}{l}
@@ -6482,7 +6482,7 @@ be of any practical use. In the case of
approximately $80\%$ of all candidate integers. The constant
\textbf{PRIME\_SIZE} is equal to the number of primes in the test base. The
array \_\_prime\_tab is an array of the first \textbf{PRIME\_SIZE} prime
numbers.
-\begin{figure}[!here]
+\begin{figure}[!h]
\begin{small}
\begin{center}
\begin{tabular}{l}
@@ -6538,7 +6538,7 @@ of a base will divide $n - 1$ which woul
integers known as Carmichael numbers will be a pseudo-prime to all valid
bases. Fortunately such numbers are extremely rare as $n$ grows
in size.
-\begin{figure}[!here]
+\begin{figure}[!h]
\begin{small}
\begin{center}
\begin{tabular}{l}
@@ -6575,7 +6575,7 @@ candidate integers. The algorithm is b
value must be equal to $-1$. The squarings are stopped as soon as $-1$ is
observed. If the value of $1$ is observed first it means that
some value not congruent to $\pm 1$ when squared equals one which cannot occur
if $n$ is prime.
-\begin{figure}[!here]
+\begin{figure}[!h]
\begin{small}
\begin{center}
\begin{tabular}{l}
--- End Message ---
