Lines Matching refs:Reduction
271 \hline Five modular reduction algorithms & X & & Faster modular exponentiation for a variety of moduli. \\
1274 \chapter{Modular Reduction}
1276 Modular reduction is process of taking the remainder of one quantity divided by another. Expressed
1277 as (\ref{eqn:mod}) the modular reduction is equivalent to the remainder of $b$ divided by $c$.
1285 fast reduction algorithms can be written for the limited range.
1287 Note that one of the four optimized reduction algorithms are automatically chosen in the modular exponentiation
1291 In order to effect an arbitrary modular reduction the following algorithm is provided.
1301 \section{Barrett Reduction}
1303 Barrett reduction is a generic optimized reduction algorithm that requires pre--computation to achieve
1312 be computed once. Modular reduction can now be performed with the following.
1375 \section{Montgomery Reduction}
1377 Montgomery is a specialized reduction algorithm for any odd moduli. Like Barrett reduction a pre--computation
1385 For the given odd moduli $a$ the precomputation value is placed in $mp$. The reduction is computed with the
1395 Montgomery reduction is faster than Barrett reduction for moduli smaller than the ``comba'' limit. With the default
1399 An important observation is that this reduction does not return $a \mbox{ mod }m$ but $aR^{-1} \mbox{ mod }m$
1411 example, to calculate $a^3 \mbox { mod }b$ using Montgomery reduction the value of $a$ can be normalized by
1489 a single final reduction to correct for the normalization and the fast reduction used within the algorithm.
1495 ``Dimminished Radix'' reduction refers to reduction with respect to moduli that are ameniable to simple
1499 As in the case of Montgomery reduction there is a pre--computation phase required for a given modulus.
1507 and does not return any error codes. After the pre--computation a reduction can be performed with the
1520 BBS cryptographic purposes. This reduction algorithm is useful for Diffie-Hellman and ECC where fixed
1523 Note that unlike Montgomery reduction there is no normalization process. The result of this function is
1545 slower than mp\_dr\_reduce but faster for most moduli sizes than the Montgomery reduction.
1562 will automatically detect the fastest modular reduction technique to use during the operation. For negative values of
