|
Addition chaining is a method of computing ax mod n
efficiently that is sometimes used in cryptographic systems. Instead
of performing a series of multiplications followed by a large
division, there are ways to minimize the size and number of
multiplications. Because the operations of multiplication and modulo
division are distributive, it is faster to take the modulus between
successive multiplications thus limiting the size of the operands
being multiplied. For instance,
a8 mod n = ((a2 mod n)2 mod n)2 mod n
If x in ax mod n is not a power of two then the binary
representation of x can be used.
a25 mod n = (a * a24) mod n
But we also know that
a24 mod n = (a8 * a16) mod n. a8is
((a2)2)2 (a(23)). Likewise
a16 = a(24).
| 
Search