Previous | ToC | Next Labs: Cryptography. Part 2. Math Alive

Modular multiplication of many numbers

On a previous page you saw that to multiply two numbers modulo A we can first take the remainders of those two numbers modulo A, and then to multiply. That means we do not need to multiply numbers bigger than A.

If we want to multiply many numbers modulo A, we can first reduce all numbers to their remainders. Then, we can take any pair of them, multiply and reduce again.

Let us now exploit this. For example, suppose we want to find

X = 36 * 53 * 91 * 17 * 22 (mod 29) .

Start by reducing every factor to its remainder after division by 29:

Modular multiplication of many numbers

We never looked at any product larger than 282.

Previous | ToC | Next Last Modified: August 2008