Lines Matching defs:Radix
2012 This notation arises within discussion of Montgomery and Diminished Radix Reduction as well as Karatsuba multiplication and squaring.
3685 \subsection{Choosing a Radix Point}
4264 \section{The Diminished Radix Algorithm}
4265 The Diminished Radix method of modular reduction \cite{DRMET} is a fairly clever technique which can be more efficient than either the Barrett
4293 \hline Algorithm \textbf{Diminished Radix Reduction}. \\
4309 \caption{Algorithm Diminished Radix Reduction}
4364 \caption{Example Diminished Radix Reduction}
4395 \subsection{Restricted Diminished Radix Reduction}
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
4434 This algorithm will perform the Dimished Radix reduction of $x$ modulo $n$. It has similar restrictions to that of the Barrett reduction
4470 To setup the restricted Diminished Radix algorithm the value $k = \beta - n_0$ is required. This algorithm is not really complicated but provided for
4497 Another algorithm which will be useful is the ability to detect a restricted Diminished Radix modulus. An integer is said to be
4498 of restricted Diminished Radix form if all of the digits are equal to $\beta - 1$ except the trailing digit which may be any value.
4520 This algorithm determines if a value is in Diminished Radix form. Step 1 rejects obvious cases where fewer than two digits are
4522 step 3 then $n$ must be of Diminished Radix form.
4531 \subsection{Unrestricted Diminished Radix Reduction}
4532 The unrestricted Diminished Radix algorithm allows modular reductions to be performed when the modulus is of the form $2^p - k$. This algorithm
4535 In general the restricted Diminished Radix reduction algorithm is much faster since it has considerably lower overhead. However, this new
4564 This algorithm quickly reduces an input $a$ modulo an unrestricted Diminished Radix modulus $n$. Division by $2^p$ is emulated with a right
4617 An integer $n$ is a valid unrestricted Diminished Radix modulus if either of the following are true.
4683 For almost every cryptographic algorithm Montgomery reduction is the algorithm of choice. The one set of algorithms where Diminished Radix reduction truly
4685 primes of the form $\beta^m - k$ can be found and shared amongst users. These primes will allow the Diminished Radix algorithm to be used in
4697 $\left [ 4 \right ]$ & Prove that the pseudo-code algorithm ``Diminished Radix Reduction'' \\
5009 except it uses either Montgomery or Diminished Radix reduction. The two latter reduction algorithms are clumped in the same exponentiation
5024 If the exponent is positive the algorithm resumes the exponentiation. Line 77 determines if the modulus is of the restricted Diminished Radix
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
5029 \item $dr = 0$ means that the modulus is not of either restricted or unrestricted Diminished Radix form.
5030 \item $dr = 1$ means that the modulus is of restricted Diminished Radix form.
5031 \item $dr = 2$ means that the modulus is of unrestricted Diminished Radix form.
5265 \hline Algorithm \textbf{Radix-$\beta$ Integer Division}. \\
5281 \caption{Algorithm Radix-$\beta$ Integer Division}
5356 \subsection{Radix-$\beta$ Division with Remainder}
5781 \subsection{Reading Radix-n Input}
5858 \subsection{Generating Radix-$n$ Output}