A Novel Method of Modular Multiplication Based on Karatsuba-like Multiplication
Zhen Gu, Shuguo Li
Abstract
In this paper, we propose a novel method of modular multiplication which embeds the modular reduction in the evaluation and interpolation parts of the Karatsuba-like multiplication. Before, the modular reduction can only be performed independently between multiplication. However, applying our method, the interpolation of the previous multiplication, modular reduction and evaluation of the next multiplication are merged as a whole step, which leads to the simplification of computations and improvement of parallelism. This method can be applied to the modular multiplication with simple moduli like NIST primes, and for general moduli, we can apply this method by using Montgomery modular multiplication instead.
Topics & Concepts
Multiplication (music)Modular arithmeticModular designReduction (mathematics)Multiplication algorithmInterpolation (computer graphics)ArithmeticComputer scienceMathematicsParallel computingArtificial intelligenceGeometryOperating systemCombinatoricsMotion (physics)Binary numberCryptography and Residue ArithmeticCoding theory and cryptographyAlgebraic Geometry and Number Theory