Lines Matching +refs:array +refs:move +refs:one +refs:row
171 reason that $7$ times $6$ is $42$. However, $42$ has two digits of precision as opposed to one digit we started with.
276 The algorithms that are presented will always include at least one ``pseudo-code'' description followed
286 the integer $x \equiv \sum_{i=0}^{n-1} x_i\beta^i$. The elements of the array $x$ are said to be the radix $\beta$ digits
318 For the purposes of this text $x_j$ will refer to the $j$'th digit of a single precision array and $\hat x_j$ will refer to
319 the $j$'th digit of a double precision array. Whenever an expression is to be assigned to a double precision
334 distinction is important as scalars are often used as array indicies and various other counters.
377 exercises ranges from one (the easiest) to five (the hardest). The following table sumarizes the
464 LibTomMath was chosen as the case study of this text not only because the author of both projects is one and the same but
532 before implementing a modular exponentiation algorithm one would implement a modular reduction algorithm.
556 the source code. For example, one day I may audit the multipliers and the next day the polynomial basis functions.
581 if one starts writing a large number too far to the right on a piece of paper they will have to erase it and move left.
615 \item The \textbf{used} parameter denotes how many digits of the array \textbf{dp} contain the digits used to represent
619 many digits are available in the array to use by functions before it has to increase in size. When the \textbf{used} count
621 array to accommodate the precision of the result.
623 \item The pointer \textbf{dp} points to a dynamically allocated array of digits that represent the given multiple
624 precision integer. It is padded with $(\textbf{alloc} - \textbf{used})$ zero digits. The array is maintained in a least
625 significant digit order. As a pencil and paper analogy the array is organized such that the right most digits are stored
626 first starting at the location indexed by zero\footnote{In C all arrays begin at zero.} in the array. For example,
639 \item The value of \textbf{alloc} may not be less than one. That is \textbf{dp} always points to a previously allocated
640 array of digits.
642 \item The value of \textbf{used} implies the digit at index $(used - 1)$ of the \textbf{dp} array is non-zero. That is,
645 \item Digits in the \textbf{dp} array at and above the \textbf{used} location must be zero.
687 \textbf{int} data type with one of the following values (fig \ref{fig:errcodes}).
883 result of an operation without loss of precision. Quite often the size of the array given by the \textbf{alloc} member
884 is large enough to simply increase the \textbf{used} digit count. However, when the size of the array is too small it
897 4. Re-allocate the array of digits $a$ to size $v$ \\
910 It is ideal to prevent re-allocations from being performed if they are not required (step one). This is useful to
1000 The purpose of algorithm mp\_init\_multi is to initialize a variable length array of mp\_int structures in a single
1007 \textbf{Input}. Variable length array $V_k$ of mp\_int variables of length $k$. \\
1008 \textbf{Output}. The array is initialized such that each mp\_int of $V_k$ is ready to use. \\
1024 The algorithm will initialize the array of mp\_int variables one at a time. If a runtime error has been detected
1036 structures in an actual C array they are simply passed as arguments to the function. This function makes use of the
1085 As can be expected this algorithm is very simple. The loop on step one is expected to iterate only once or twice at
1098 important since if the \textbf{used} is zero the test on the right would fetch below the array. That is obviously
1173 step one of the mp\_copy algorithm the return of mp\_grow is not explicitly checked to ensure it succeeded. Text space is
1186 mp\_int structures passed to a function are one and the same. For this case it is optimal to return immediately without
1221 array of digits within an mp\_int structure directly. It may seem that a pointer alias is strictly not required
1278 such this algorithm will perform two operations in one step.
1418 3. $a.used \leftarrow \left \lbrace \begin{array}{ll}
1421 \end{array} \right .$ \\
1442 check if the resulting digit is zero or not. If it is not then we set the \textbf{used} count to one, otherwise
1448 One important limitation of this function is that it will only set one digit. The size of a digit is not fixed, meaning source that uses
1502 positions. If any leading digit of one integer is greater than a digit in the same position of another integer then obviously it must be greater.
1561 smaller than $a.used$, meaning that undefined values will be read from $b$ past the end of the array of digits.
1608 $\left [ 2 \right ]$ & Modify algorithm mp\_set\_int to accept as input a variable length array of bits. \\
1712 one digit of the summand. First
1717 for one of the inputs that has more digits. A simplified addition loop is then used to essentially copy the remaining digits
1817 significant bit. Thus, the high order bits of the mp\_digit that are not part of the actual digit will either be all zero, or all one. All that
1818 is needed is a single zero or one bit for the carry. Therefore a single logical shift right by $\gamma - 1$ positions is sufficient to extract the
1841 the bits above the $\lg(\beta)$'th bit will be set to one after a carry occurs from subtraction. This carry
1854 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}
1956 \hspace{6mm}2.2.1 $c.sign \leftarrow \left \lbrace \begin{array}{ll}
1959 \end{array} \right .$ \\
2117 could be written to work from the trailing digit to the leading digit however, it would have to stop one short of $a.used - 1$ digits to prevent
2118 reading past the end of the array of digits.
2136 Converting from an array of digits to polynomial basis is very simple. Consider the integer $y \equiv (a_2, a_1, a_0)_{\beta}$ and recall that
2142 Given a polynomial in $x$ such as $f(x) = a_n x^n + a_{n-1} x^{n-1} + ... + a_0$ multiplying by $x$ amounts to shifting the coefficients up one
2184 The loop on step 7 copies the digit from the tail to the head. In each iteration the window is moved down one digit. The last loop on
2246 If the input $b$ is less than one the algorithm quickly returns without performing any work. If the \textbf{used} count is less than or equal
2491 For centuries general purpose multiplication has required a lengthly $O(n^2)$ process, whereby each digit of one multiplicand has to be multiplied
2590 Each row of the product is added to the result after being shifted to the left (\textit{multiplied by a power of the radix}) by the appropriate
2675 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
2742 Place an array of \textbf{MP\_WARRAY} single precision digits named $W$ on the stack. \\
2779 loop we want to produce one column per pass. This allows the accumulator $\_ \hat W$ to be placed in CPU registers and
2786 The variable $iy$ is the minimum digits we can read from either $a$ or $b$ before running out. Computing one column at a time
2787 means we have to scan one integer upwards and the other downwards. $a$ starts at $tx$ and $b$ starts at $ty$. In each
2788 pass we are producing the $ix$'th output column and we note that $tx + ty = ix$. As we move $tx$ upwards we have to
2789 move $ty$ downards so the equality remains valid. The $iy$ variable is the number of iterations until
2813 implementation was ``row--major'' which means it adds to each of the columns in each pass. After the outer loop it would then fix
2815 one mp\_word per iteration. On processors such as the Athlon XP and P4 this did not matter much since the cache bandwidth
3051 of two, two divisions by three and one multiplication by three. All of these $19$ sub-operations require less than quadratic time, meaning that
3138 that row $1$ must be subtracted from row $4$ and simultaneously row $0$ subtracted from row $3$.
3242 represent the number being squared. The first observation is that in row $k$ the $2k$'th column of the product has a $\left (x_k \right)^2$ term in it.
3244 The second observation is that every column $j$ in row $k$ where $j \ne 2k$ is part of a double product. Every non-square term of a column will
3246 products and at most one square (\textit{see the exercise section}).
3248 The third and final observation is that for row $k$ the first unique non-square term, that is, one that hasn't already appeared in an earlier row,
3249 occurs at column $2k + 1$. For example, on row $1$ of the previous squaring, column one is part of the double product with column one from row zero.
3250 Column two of row one is a square and column three is the first unique column.
3300 the inner loop computes the columns of the partial result. Step 4.1 and 4.2 compute the square term for each row, and step 4.3 and 4.4 propagate
3331 The first obvious solution is to make an array of mp\_words which will hold all of the columns. This will indeed eliminate all of the carry
3336 However, we cannot simply double all of the columns, since the squares appear only once per row. The most practical solution is to have two
3337 mp\_word arrays. One array will hold the squares and the other array will hold the double products. With both arrays the doubling and
3348 Place an array of \textbf{MP\_WARRAY} mp\_digits named $W$ on the stack. \\
3515 shift the input into the two halves. The loop from line 54 to line 70 has been modified since only one input exists. The \textbf{used}
3561 This algorithm computes the square of the input using one of four different algorithms. If the input is very large and has at least
3578 & of double products and at most one square is stated. Prove this statement. \\
3645 equivalent to one than $2^q/b$ is equivalent to the fixed point approximation of $1/b$ using real arithmetic. Using this fact dividing an integer
3673 Provided that $2^q \ge a$ this algorithm will produce a quotient that is either exactly correct or off by a value of one. In the context of Barrett
3711 by as much as one (\textit{provided the radix point is chosen suitably}) and now that the lower irrelevent digits have been trimmed the quotient
3712 can be off by an additional value of one for a total of at most two. This implies that
3799 First the modulus $b$ is assumed to be positive and greater than one. If the modulus were less than or equal to one than subtracting
3876 \textbf{Fact 1.} Adding $n$ to $x$ does not change the residue since in effect it adds one to the quotient $\lfloor x / n \rfloor$. Another way
3905 The algorithm reduces the input one bit at a time using the two congruencies stated previously. Inside the loop $n$, which is odd, is
3950 \hspace{3mm}1.1 If the $t$'th bit of $x$ is one then \\
4125 The multiplication $\mu n \beta^{ix}$ is performed in one step in the inner loop. The alias $tmpx$ refers to the $ix$'th digit of $x$ and
4151 Place an array of \textbf{MP\_WARRAY} mp\_word variables called $\hat W$ on the stack. \\
4153 Copy the digits of $x$ into the array $\hat W$ \\
4193 As in the other Comba reduction algorithms there is a $\hat W$ array which stores the columns of the product. It is initially filled with the
4214 The $\hat W$ array is first filled with digits of $x$ on line 48 then the rest of the digits are zeroed on line 55. Both loops share
4222 modulo $\beta$ and shifts them $k$ places at the same time. The alias $\_ \hat W$ actually refers to the array $\hat W$ starting at the $n.used$'th
4377 Division in general is a very expensive operation to perform. The one exception is when the division is by a power of the radix of representation used.
4382 However, there is one operation related to division of power of twos that is even faster than this. If $n = \beta^p$ then the division may be
4607 is sufficient to solve for $k$. Alternatively if $n$ has more than one digit the value of $k$ is simply $\beta - n_0$.
4620 \item The number has only one digit.
4621 \item The number has more than one digit and every bit from the $\beta$'th to the most significant is one.
4625 one digit than it will always be of the correct form. Otherwise all of the bits above the first digit must be one. This arises from the fact
4683 For almost every cryptographic algorithm Montgomery reduction is the algorithm of choice. The one set of algorithms where Diminished Radix reduction truly
4705 Exponentiation is the operation of raising one variable to the power of another, for example, $a^b$. A variant of exponentiation, computed
4821 on step 3.1. In the following step if the most significant bit of $b$ is one the copy of $a$ is multiplied against $c$. The value
4822 of $b$ is shifted left one bit to make the next bit down from the most signficant bit the new most significant bit. In effect each
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
4975 one of the algorithms presented in chapter six.
5010 algorithm since their arguments are essentially the same (\textit{two mp\_ints and one mp\_digit}).
5025 form. If it is not line 70 attempts to determine if it is of a unrestricted Diminished Radix form. The integer $dr$ will take on one
5048 2. $winsize \leftarrow \left \lbrace \begin{array}{ll}
5056 \end{array} \right .$ \\
5057 3. Initialize $2^{winsize}$ mp\_ints in an array named $M$ and one mp\_int named $\mu$ \\
5127 15. Clear $res$, $mu$ and the $M$ array. \\
5141 larger the window size becomes. After a window size $winsize$ has been chosen an array of $2^{winsize}$ mp\_int variables is allocated. This
5172 After a digit is made available step 12.3 will extract the most significant bit of the current digit and move all other bits in the digit
5199 from smallest to greatest so that in each \textbf{if} statement only one condition must be tested. For example, by the \textbf{if} statement
5205 The for loop on line 61 initializes the $M$ array while lines 72 and 77 through 86 initialize the reduction
5375 6. $sign \leftarrow \left \lbrace \begin{array}{ll}
5378 \end{array} \right .$ \\
5452 First the divisor $b$ must be non-zero which is enforced in step one. If the divisor is larger than the dividend than the quotient is implicitly
5474 After both phases of estimation the quotient digit may still be off by a value of one\footnote{This is similar to the error introduced
5563 multiplication algorithm. Essentially this algorithm is a modified version of algorithm s\_mp\_mul\_digs where one of the multiplicands
5564 only has one digit.
5932 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
6033 step five both $a$ and $b$ are odd. Therefore, the diffrence $b - a$ must be even which means that each iteration removes one bit from the
6083 The first two steps handle the cases where either one of or both inputs are zero. If either input is zero the greatest common divisor is the
6089 six and seven ensure that the $u$ and $v$ respectively have no more factors of two. At most only one of the while--loops will iterate since
6114 the number of factors will not exceed the maximum value of a C ``int'' data type\footnote{Strictly speaking no array in C may have more than
6129 Linear Feedback Shift Registers (LFSR) tend to use registers with periods which are co-prime (\textit{e.g. the greatest common divisor is one.}).
6169 a^{(p-1)/2} \equiv \begin{array}{rl}
6173 \end{array} \mbox{ (mod }p\mbox{)}
6304 Step numbers one and two handle the trivial cases of $a = 0$ and $a = 1$ respectively. Step five determines the number of two factors in the
6305 input $a$. If $k$ is even than the term $\left ( { 2 \over p } \right )^k$ must always evaluate to one. If $k$ is odd than the term evaluates to one
6306 if $p_0$ is congruent to one or seven modulo eight, otherwise it evaluates to $-1$. After the the $\left ( { 2 \over p } \right )^k$ term is handled
6307 the $(-1)^{(p-1)(a'-1)/4}$ is computed and multiplied against the current product $s$. The latter term evaluates to one if both $p$ and $a'$
6308 are congruent to one modulo four, otherwise it evaluates to negative one.
6310 By step nine if $a'$ does not equal one a recursion is required. Step 9.1 computes $p' \equiv p \mbox{ (mod }a'\mbox{)}$ and will recurse to compute
6332 $k$ is even and the value is one. Otherwise, the value of $s$ depends on which residue class $p$ belongs to modulo eight. The value of
6335 Finally, if $a1$ does not equal one the algorithm must recurse and compute $\left ( {p' \over a'} \right )$.
6433 If $v$, the greatest common divisor of $a$ and $b$ is not equal to one then the algorithm will report an error as no inverse exists. Otherwise, $C$
6455 A non-zero integer $a$ is said to be prime if it is not divisible by any other integer excluding one and itself. For example, $a = 7$ is prime
6483 array \_\_prime\_tab is an array of the first \textbf{PRIME\_SIZE} prime numbers.
6530 The Fermat test is probably one the oldest tests to have a non-trivial probability of success. It is based on the fact that if $n$ is in
6576 some value not congruent to $\pm 1$ when squared equals one which cannot occur if $n$ is prime.
6609 This algorithm performs one trial round of the Miller-Rabin algorithm to the base $b$. It will set $c = 1$ if the algorithm cannot determine