Выполнение операции А х В mod n обычным путем, то есть умножение А на В и затем применение модульной редукции, не является ни быстрым и экономичным способом умножения. Данное вычисление гораздо лучше выполнить, используя, например, разложение числа В вида В = bnA,n + + Ъп_{\п~1 + ... + htX + b0 и последовательное умножение вида с = Abj (при этом получаются числа с размерностью п + 1), а затем вычислить mod n. (рис. 1.14).