Partially Interleaved Modular Karatsuba-Ofman Multiplication

We describe a method of performing modular multiplication that has various applications in the field of modern cryptography and coding theory. The proposed algorithm, which combines the Karatsuba-Ofman multiplier and bipartite modular reduction, presents an interleaved processing on the upper most level of Karatsuba-Ofman's recursion. The method provides an efficient and highly parallel modular arithmetic for both hardware and software realizations of public-key cryptosystems, such as today's dominating RSA and Diffie-Hellman algorithms.