modular arithmetic

(redirected from Modular multiplication)
Also found in: Dictionary.

modular arithmetic

(Or "clock arithmetic") A kind of integer arithmetic that reduces all numbers to one of a fixed set [0..N-1] (this would be "modulo N arithmetic") by effectively repeatedly adding or subtracting N (the "modulus") until the result is within this range.

The original mathematical usage considers only __equivalence__ modulo N. The numbers being compared can take any values, what matters is whether they differ by a multiple of N. Computing usage however, considers modulo to be an operator that returns the remainder after integer division of its first argument by its second.

Ordinary "clock arithmetic" is like modular arithmetic except that the range is [1..12] whereas modulo 12 would be [0..11].
Mentioned in ?
References in periodicals archive ?
absolute value of n + 1/4] -1) modular multiplications are needed to evaluate Equation (15).
The multiplier of Figure 4 performs the modular multiplication X x Y mod M in three main steps:
Algorithms that formalize the operation of modular multiplication generally consist of two steps: one generates the product P = A x B and the other reduces this product P modulo M.
One of the widely used algorithms for efficient modular multiplication is the Montgomery's algorithm [18].
lt;/pre> <p>In order to yield the right result, we need an extra Montgomery modular multiplication by the constant [2.
Figure 32 shows the behavior of the multiplier during the first modular multiplication (note that signal step is not set).
As before, Figure 34 shows the behavior of the multiplier during the first modular multiplication and Figure 35 shows the results of the second modular multiplication (note that signal step is set).
n+1]) of the modular multiplication is yield after 2n + 2 + j after bits [b.
The modular multiplication algorithm and respective hardware can be further improved if the representation of the operands is considered.
In this paper we surveyed most known and recent methods for efficient modular multiplication.
We explained that the modular multiplication A x B mod M can be performed in two different ways: obtaining the product then reducing it; or obtaining the reduced product directly.
The implementation of the modular multiplication using Karatsuba-Ofman's method for multiplying and Barrett's method for reducing the obtained result presents a shorter signal propagation delay than using Booth's method together with Barrett's method, without much increase in hardware area requirements.

Full browser ?