Lines Matching +refs:term +refs:write +refs:input +refs:ring
155 and at least review all of it, and perhaps write some bits too. There's still a long way to go with it, and I have watched a number of close
248 inputs. That is, the same algorithms based on multiple precision integers can accomodate any reasonable size input
291 The term ``mp\_int'' shall refer to a composite structure which contains the digits of the integer it represents, as well
301 to solve a given problem. When an algorithm is described as accepting an integer input it is assumed the input is
495 effect a math error (i.e. invalid input, heap error, etc) can cause a program to stop functioning which is definitely
580 The human analogy of this third property is ensuring there is enough space on the paper to write the integer. For example,
655 structures. That means that the source (input) operands are placed on the left and the destination (output) on the right.
695 \hline \textbf{MP\_VAL} & One of the input value(s) was invalid \\
762 manipulte it. It is assumed that the input may not have had any of its members previously initialized which is certainly
763 a valid assumption if the input resides on the stack.
777 of the original condition of the input.
943 of input mp\_ints to a given algorithm. The purpose of algorithm mp\_init\_size is similar to mp\_init except that it
972 digits allocated can be controlled by the second input argument $b$. The input size is padded upwards so it is a
977 particular algorithm is useful if it is known ahead of time the approximate size of the input. If the approximation is
1185 Occasionally a dependent algorithm may copy an mp\_int effectively into itself such as when the input and output
1348 This algorithm computes the absolute of an mp\_int input. First it copies $a$ over $b$. This is an example of an
1365 the negative of an mp\_int input.
1389 This algorithm computes the negation of an input. First it copies $a$ over $b$. If $a$ has no used digits then
1453 data type as input and will always treat it as a 32-bit integer.
1608 $\left [ 2 \right ]$ & Modify algorithm mp\_set\_int to accept as input a variable length array of bits. \\
1702 will simply add all of the smallest input to the largest input and store that first part of the result in the
1703 destination. Then it will apply a simpler addition loop to excess digits of the larger input.
1706 inputs. The variable $x$ will be an mp\_int alias for the largest input or the second input $b$ if they have the
1731 Note that $x$ is a pointer to an mp\_int assigned to the largest input, in effect it is a local alias. Next we
1740 both inputs until the smallest input runs out of digits. Similarly the conditional addition loop
1821 If $b$ has a smaller magnitude than $a$ then step 9 will force the carry and copy operation to propagate through the larger input $a$ into $c$. Step
1913 Figure~\ref{fig:AddChart} lists all of the eight possible input combinations and is sorted to show that only three
2059 Step 1 and 2 grow the input as required to accomodate the maximum number of \textbf{used} digits in the result. The initial \textbf{used} count
2078 This implementation is essentially an optimized implementation of s\_mp\_add for the case of doubling an input. The only noteworthy difference
2207 window of exactly $b$ digits over the input.
2243 This algorithm divides the input in place by the $b$'th power of $x$. It is analogous to dividing by a $\beta^b$ but much quicker since
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
2247 to the shift count $b$ then it will simply zero the input and return.
2264 the upper digits of the input to make sure the result is correct.
2320 This algorithm is loosely measured as a $O(2n)$ algorithm which means that if the input is $n$-digits that it takes $2n$ ``time'' to
2330 The shifting is performed in--place which means the first step (line 25) is to copy the input to the
2376 This algorithm will divide an input $a$ by $2^b$ and produce the quotient and remainder. The algorithm is designed much like algorithm
2442 than the input we just mp\_copy() the input and return right away. After this point we know we must actually
2463 & any $n$-bit input. Note that the time of addition is ignored in the \\
2503 multiplications are required. More specifically for a $m$ and $n$ digit input $m \cdot n$ single precision multiplications are required. To
2509 modification will become evident during the discussion of Barrett modular reduction. Recall that for a $n$ and $m$ digit input the product
2563 input is less than $\delta$, then the Comba method may be used instead. After the Comba method is ruled out, the baseline algorithm begins. A
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
2731 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
2814 the carries. This was very fast except it had an annoying drawback. You had to read a mp\_word and two mp\_digits and write
2842 When picking points to gather relations there are always three obvious points to choose, $y = 0, 1$ and $ \infty$. The $\zeta_0$ term
2843 is simply the product $W(0) = w_0 = a_0 \cdot b_0$. The $\zeta_1$ term is the product
2850 $\left (2^q \right )^{2n} \cdot \zeta_{2^{-q}}$ for small values of $q$. The term ``mirror point'' stems from the fact that
2941 By adding the first and last equation to the equation in the middle the term $w_1$ can be isolated and all three coefficients solved for. The simplicity
2956 Split the input. e.g. $a = x1 \cdot \beta^B + x0$ \\
2970 Calculate the middle term. \\
2994 be used for both of the inputs meaning that it must be smaller than the smallest input. Step 3 chooses the radix point $B$ as half of the
2995 smallest input \textbf{used} count. After the radix point is chosen the inputs are split into lower and upper halves. Step 4 and 5
3202 available when the input is of appropriate size. The \textbf{sign} of the result is not set until the end of the algorithm since algorithm
3225 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$
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
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,
3253 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
3295 This algorithm computes the square of an input using the three observations on squaring. It is based fairly faithfully on algorithm 14.16 of HAC
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
3317 Inside the outer loop (line 34) the square term is calculated on line 37. The carry (line 44) has been
3384 This algorithm computes the square of an input using the Comba technique. It is designed to be a replacement for algorithm
3385 s\_mp\_sqr when the number of input digits is less than \textbf{MP\_WARRAY} and less than $\delta \over 2$.
3395 Finally the last difference is the addition of the ``square'' term outside the inner loop (step 5.8). We add in the square
3396 only to even outputs and it is the square of the term at the $\lfloor ix / 2 \rfloor$ position.
3423 Karatsuba multiplication, this algorithm can be applied recursively on the input and will achieve an asymptotic running time of
3446 Split the input. e.g. $a = x1\beta^B + x0$ \\
3457 Compute the middle term. \\
3475 This algorithm computes the square of an input $a$ using the Karatsuba technique. This algorithm is very similar to the Karatsuba based
3478 The radix point for squaring is simply placed exactly in the middle of the digits when the input has an odd number of digits, otherwise it is
3502 This results in a cutoff point around $n = 2$. As a consequence it is actually faster to compute the middle term the ``long way'' on processors
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
3700 ``might as well be zero'' they might as well not be there in the first place. Let $q_0 = \lfloor a/\beta^{m-1} \rfloor$ represent the input
3741 After the quotient has been calculated it is used to reduce the input. As previously noted the algorithm is not exact and it can be off by a small
3771 Subtract the multiple of modulus from the input. \\
3795 This algorithm will reduce the input $a$ modulo $b$ in place using the Barrett algorithm. It is loosely based on algorithm 14.42 of HAC
3800 a multiple of it would either accomplish nothing or actually enlarge the input. The input $a$ must be in the range $0 \le a < b^2$ in order
3869 form of reduction in common use. It computes a modular residue which is not actually equal to the residue of the input yet instead equal to a
3873 $n$ must be odd. The variable $x$ will represent the quantity of which the residue is sought. Similar to the Barrett algorithm the input
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
3988 With this algorithm a single shift right at the end is the only right shift required to reduce the input instead of $k$ right shifts inside the
4051 The baseline Montgomery reduction algorithm will produce the residue for any size input. It is designed to be a catch-all algororithm for
4098 This algorithm reduces the input $x$ modulo $n$ in place using the Montgomery reduction algorithm. The algorithm is loosely based
4100 restrictions on this algorithm are fairly easy to adapt to. First $0 \le x < n^2$ bounds the input to numbers in the same range as
4105 the size of the input. This algorithm is discussed in sub-section 6.3.3.
4189 on the input as the baseline reduction algorithm. An additional two restrictions are imposed on this algorithm. The number of digits $k$ in the
4274 of the above equation is very simple. First write $x$ in the product form.
4326 Since $k^2$ is going to be considerably smaller than $n$ that term will always be zero. The value of $x$ after step 3 is bounded trivially as
4334 sum in step 4 will exceed $n - k$. In practice fewer than three passes of the algorithm are required to reduce virtually every input in the
4386 Throughout the next section the term ``restricted modulus'' will refer to a modulus of the form $\beta^p - k$ whereas the term ``unrestricted
4396 The restricted Diminished Radix algorithm can quickly reduce an input modulo a modulus of the form $n = \beta^p - k$. This algorithm can reduce
4397 an input $x$ within the range $0 \le x < n^2$ using only a couple passes of the algorithm demonstrated in figure~\ref{fig:DR}. The implementation
4439 the term at the $m+i$'th position which is subsequently multiplied by $k$ and added to the term at the $i$'th position. After the loop the $m$'th
4564 This algorithm quickly reduces an input $a$ modulo an unrestricted Diminished Radix modulus $n$. Division by $2^p$ is emulated with a right
4624 If either condition is true than there is a power of two $2^p$ such that $0 < 2^p - n < \beta$. If the input is only
4706 in a finite field or ring, is called modular exponentiation. This latter style of operation is typically used in public key
4729 The term $a^{2^i}$ can be found from the $i - 1$'th term by squaring the term since $\left ( a^{2^i} \right )^2$ is equal to
4733 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
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
4970 Modular exponentiation is essentially computing the power of a base within a finite field or ring. For example, computing
5019 In order to keep the algorithms in a known state the first step on line 29 is to reject any negative modulus as input. If the exponent is
5345 For the purposes of division a normalized input is when the divisors leading digit $x_n$ is greater than or equal to $\beta / 2$. By multiplying both
5521 the helper functions assume the single digit input is positive and will treat them as such.
5720 This algorithm finds the integer $n$'th root of an input using the Newton-Raphson approach. It is partially optimized based on the observation
5726 root. Ideally this algorithm is meant to find the $n$'th root of an input where $n$ is bounded by $2 \le n \le 5$.
5847 string to indicate the value is negative, otherwise it is assumed to be positive. The algorithm will read up to $sn$ characters from the input
5849 as part of larger input without any significant problem.
5894 successive powers of $\lfloor a / r^k \rfloor$ the input modulo $r$ until $r^k > a$. Note that instead of actually dividing by $r^k$ in
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
6037 The algorithms presented so far cannot handle inputs which are zero or negative. The following algorithm can handle all input cases properly
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
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
6106 This function makes use of the macros mp\_iszero and mp\_iseven. The former evaluates to $1$ if the input mp\_int is equivalent to the
6107 integer zero otherwise it evaluates to $0$. The latter evaluates to $1$ if the input mp\_int represents a non-zero even integer otherwise
6108 it evaluates to $0$. Note that just because mp\_iseven may evaluate to $0$ does not mean the input is odd, it could also be zero. The three
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'$
6323 The two simple cases of $a = 0$ and $a = 1$ are handled at the very beginning to simplify the algorithm. If the input is non-trivial the algorithm
6343 denoted as $b = a^{-1}$. Technically speaking modular inversion is a well defined operation for any finite ring or field not just for rings and
6346 The simplest approach is to compute the algebraic inverse of the input. That is to compute $b \equiv a^{\Phi(p) - 1}$. If $\Phi(p)$ is the
6435 within $1 \le a^{-1} < b$. Step numbers twelve and thirteen adjust the inverse until it is in range. If the original input $a$ is within $0 < a < p$
6689 \input{tommath.ind}