Modular multiplication process includes decomposition of large numbers into numbers in different base, to effect multiplication

摘要

The cryptographic process provides modular multiplication on numbers. The process includes decomposition of the numbers in to another base. MultModDiv operations are then carried out on the numbers. The cryptographic process provides modular multiplication on numbers (A x B mod N). The process includes decomposition of the numbers (A, B, N of 2xn bits) in to a base, U, such that A=A 1xU+A 0, B=B 1xU+B 0 and N=N 1xU+N 0, A 1, A 0, B 1, B 0, N 1 and N 0 all being words of n bits. MultModDiv operations are then carried out on the numbers A 1, A 0, B 1, B 0, N 1 and N 0, the elementary operation MultModDiv being defined by MultModDiv(X,Y,Z = ([(XxY)/Z], (XxY) mod Z ), X, Y & Z being integer numbers of at least n bits.