Modular Multiplication Using Montgomery MethodModular Multiplication and Reduction is achieved SimultaneouslyDetails of I/P and O/PTransformation to other domainMultiplication ProcessThe Logic Behind The ProcessCalculation of 2^2k Mod N Comparison of Implementation with NTL Library Functions.Comparison FactorsConclusionModular Multiplication Using Montgomery MethodECE 543/646 (Fall 2000) Ramprasad GowrishankarModular Multiplication and Reduction is achieved Simultaneously Reported to be the fastest Algorithm for Modular Multiplication.Details of I/P and O/P♦ The inputs are Arguments A and B.♦ The output required is C = A*B Mod N.♦ The arguments are transferred to another domain where the exponentiation is done much faster.Transformation to other domain♦ First A’ is calculated from A asA’ = A*2^k Mod N.♦ Then B’ is calculated from B asB’ = B*2^k Mod N.Now in this domain Multiplication is faster Multiplication and reduction is done simultaneously.Multiplication Process♦ In the other domain the Multiplication is performed as follows.C'=A' * B' * 2^-n mod N = (A*B) * 2^n mod N = C*2^n mod N♦ This is then Transferred to the original Domain by Multiplication by 1 in the New domain.The Logic Behind The Process♦ Multiple Precision Multiplication for big Integers Involve Bitwise Multiplication.♦ The given Integers are Separated into group of Bits( 8 bits each) .♦ The LSB of the Multiplicand group is taken and it is multiplied one round with the other integer.Details of Modular ReductionResult after the first roundL1.NReduced result 000000000000Result after the second roundL2.NReduced result 000000000000Final Result C’ + k bits of ZerosCalculation of 2^2k Mod N♦ For calculating the A’ value , first the 2^2k Mod N is calculated , since this is a large number Classical Algorithm is used to calculate this value.♦ After obtaining the 2^2k Mod N , there is a Montgomery Multiplication Between A and the Output from the Classical Algorithm, which gives the value of A’.♦ B’ is Obtained in the same way as A’.Comparison of Implementation with NTL Library Functions.♦NTL is a high-performance, portable C++ library providing data structures and algorithms for arbitrary length integers,vectors, matrices, and polynomials over the integers and over finite fields and for arbitrary precision floating point arithmetic. INTRODUCTION TO NTL LIBRARYComparison Factors♦ The comparison factors are (a) length of operands(b) Speed of ExponentiationNTL supports modular integer arithmetic The class ZZ_p represents the integersmod p. Despite the notation, p need not in general be prime, except in situations where this is mathematically required.♦ NTL provides a routine for A^E Mod N in the Documentation.The Program is called in a time routine and the length of operands and the Time curve is obtained for NTL function.♦ The length of operands in NTL is Variable and it can handle a large range of Inputs.The range of inputs in Montgomery Implementation is around 1024 bits.Curve Between Length of Operands and TimeLengthof OperandsBytesTime m SecMontgomery ImplementationCurve Between Length of Operands and TimeLengthof OperandsBytesTime m SecNTL ImplementationConclusion♦ Problems Encountered The main hindrance that was faced was UNDERSTANDING the Algorithm Calculation of 2^2k Mod N. Calculation of Time. Getting the Libraries to work.♦ Points Inferred To implement an Algorithm ,one must toil to understand it. Appreciation for Prof. Kris gaj for answering my silly questions.☺ Greatest regard for people who get things
View Full Document
Unlocking...