hcrypto/libtommath/tommath.tex

5 \usepackage{color}
206 see fit.}  can only represent values up to $10^{19}$ as shown in figure \ref{fig:ISOC}. On its own the C language is
549 \includegraphics{pics/design_process.ps}
563 be used to represent values larger than their precision will allow. The purpose of multiple precision algorithms is
564 to use fixed precision data types to create and manipulate multiple precision integers which may represent values
687 \textbf{int} data type with one of the following values (fig \ref{fig:errcodes}).
736 structure are set to valid values.  The mp\_init algorithm will perform such an action.
869 Now that the digits have been cleared and deallocated the other members are set to their final values (lines 36 and 37).
914 This helps prevent many trivial reallocations that would grow an mp\_int by trivially small values.
918 assumed to contain undefined values they are initially set to zero.
1131 mp\_int structures, assigning small values to mp\_int structures and comparisons of the values mp\_int structures
1402 have to make sure that only non--zero values get a \textbf{sign} of \textbf{MP\_NEG}.  If the mp\_int is zero
1561 smaller than $a.used$, meaning that undefined values will be read from $b$ past the end of the array of digits.
1754 the range $0 \le x < 2\beta$ for the algorithms to work correctly.  However, it is allowable that a mp\_digit represent a larger range of values.  For
2062 Step 6 is an optimization implementation of the addition loop for this specific case.  That is since the two values being added together
2179 typically used on values where the original value is no longer required.  The algorithm will return success immediately if
2190 \includegraphics{pics/sliding_window.ps}
2336 loop (lines 46 to 76) we make use of pre--computed values $shift$ and $mask$.   These are used to
2451 $\left [ 3 \right ] $ & Devise an algorithm that performs $a \cdot 2^b$ for generic values of $b$ \\
2455                       & weight values such as $3$, $5$ and $9$.  Extend it to handle all values \\
2458 $\left [ 2 \right ] $ & Modify the preceding algorithm to handle values of the form \\
2470 $\left [ 2 \right ] $ & Devise a chart to find optimal values of $k$ for the previous problem \\
2832 However, numerical analysis theory indicates that only $2n + 1$ distinct points in $W(x)$ are required to determine the values of the $2n + 1$ unknown
2833 coefficients.   This means by finding $\zeta_y = W(y)$ for $2n + 1$ small values of $y$ the coefficients of $W(x)$ can be found with
2849 If more points are required they should be of small values and powers of two such as $2^q$ and the related \textit{mirror points}
2850 $\left (2^q \right )^{2n}  \cdot \zeta_{2^{-q}}$ for small values of $q$.  The term ``mirror point'' stems from the fact that
2859 Using such points will allow the values of $f(y)$ and $g(y)$ to be independently calculated using only left shifts.  For example, when $n = 2$ the
2865 summarizes the exponents for various values of $n$.
2910 \item  To a lesser extent memory bandwidth and function call overheads.  Provided the values are in the processor cache this is less of an
2916 is too low then there will be values of $m$ such that $m > y$ and the Comba method is still faster.  Finding the cutoff points is fairly simple when
3162 After this point we solve for the actual values of $w1, w2$ and $w3$ by reducing the $5 \times 5$ system which is relatively
4201 how the upper bits of those same words are not reduced modulo $\beta$.  This is because those values will be discarded shortly and there is no
4785 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
4866 The squaring on step 2.1 can be calculated by squaring the value $c$ successively $k$ times.  If the values of $a^g$ for $0 < g < 2^k$ have been
4877 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$
4904 this is a table for all values of $g$ where the most significant bit of $g$ is a one.  However, in order for this to be allowed in the
4905 algorithm values of $g$ in the range $0 \le g < 2^{k-1}$ must be avoided.
4907 Table~\ref{fig:OPTK2} lists optimal values of $k$ for various exponent sizes and compares the work required against algorithm~\ref{fig:KARY}.
5021 the modular inverse of $G$ and $tmpX$ is assigned the absolute value of $X$.  The algorithm will recuse with these new values with a positive
5026 of three values.
5142 table will hold the values of $g^x \mbox{ (mod }p\mbox{)}$ for $2^{winsize - 1} \le x < 2^{winsize}$.
5182 \includegraphics{pics/expt_state.ps}
5307 The value of the estimation may off by a few values in either direction and in general is fairly correct.  A simplification \cite[pp. 271]{TAOCPV2}
5316 $-x_s + 1$ arises from the fact that a truncated integer division will give the same quotient for at most $x_s - 1$ values.  Next a series of
5456 divisor $y$ and dividend $x$ are made as well.  The core of the division algorithm is an unsigned division and will only work if the values are
5457 positive.  Now the two values $x$ and $y$ must be normalized such that the leading digit of $y$ is greater than or equal to $\beta / 2$.
5547 This algorithm initiates a temporary mp\_int with the value of the single digit and uses algorithm mp\_add to add the two values together.
5725 The initial value of the approximation is t$2 = 2$ which allows the algorithm to start with very small values and quickly converge on the
5738 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
5782 For the purposes of this text we will assume that a simple lower ASCII map (\ref{fig:ASC}) is used for the values of from $0$ to $63$ to
6084 largest input or zero if they are both zero.  If the inputs are not trivial than $u$ and $v$ are assigned the absolute values of
6113 zero bits in both.  The local integer $k$ is used to keep track of how many factors of $2$ are pulled out of both values.  It is assumed that
6117 At this point there are no more common factors of two in the two values.  The divisions by a power of two on lines 62 and 68 remove
6120 place of the full signed routines since both values are guaranteed to be positive and the result of the subtraction is guaranteed to be non-negative.
6325 the values it may obtain are merely $-1$, $0$ and $1$.
6475 The benefit of this test is that trial division by small values is fairly efficient.  Specially compared to the other algorithms that will be
6516 The algorithm defaults to a return of $0$ in case an error occurs.  The values in the prime table are all specified to be in the range of a
6610 if $b$ is composite or $c = 0$ if $b$ is provably composite.  The values of $s$ and $r$ are computed such that $a' = a - 1 = 2^sr$.