next up previous contents index Search
Next: Source Code Up: 0.5 Miscellaneous Algorithms Previous: Source Code

0.5.7 Addition Chaining

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).

Scott Gasch