### Montgomery multiplication Algorithm

```Montgomery multiplication Algorithm
Under supervision of :
2nd. Semister,1392-93
Sharif University of Technology
1
Main Topic

Montgomery modular multiplication algorithm
Main Article: “Montgomery Multiplication in GF(2k)”
Written by: Cetin K. KOC and Tolga Acar,1998
Sharif University of Technology
2
Montgomery multiplication algorithm
Outline

Introduction

Montgomery modular multiplication of integers

Montgomery modular multiplication in GF(2k)

Conclusion
Sharif University of Technology
3
Montgomery multiplication algorithm
Introduction
• The importance and applications of the arithmetic operations in the
Galois field GF(2k) in :
•
•
•
•
Coding theory
Computer algebra
Cryptography
….
• Importance of the exponentiation
• Using a series of multiplication for The exponentiation
Sharif University of Technology
4
Montgomery multiplication algorithm
Introduction
• Cryptographic applications require fast arithmetic operations
• Proposed an effective modular multiplication of integers by P.L. Montgomery 1985
• Conversion to the Montgomery domain :
a : an intger
M : modulus
a  ar mod M
2 n 1  M  2 n
n
r2
Sharif University of Technology
5
Montgomery multiplication algorithm
Introduction
0  0 *16 mod 11  0
1  1*16 mod 11  5
• Example:
M = 11 , r = 24 = 16
2  2 *16 mod 11  10
3  3 *16 mod 11  4
4  4 *16 mod 11  9
• There is a one-to-one correspondence
between integers and Montgomery
residues for 0 < a < M-1
5  5 *16 mod 11  3
6  6 *16 mod 11  8
7  7 *16 mod 11  2
8  8 *16 mod 11  7
9  9 *16 mod 11  1
10  10 *16 mod 11  6
Sharif University of Technology
6
Montgomery multiplication algorithm
Outline

Introduction

Montgomery modular multiplication of integers

Montgomery modular multiplication in GF(2k)

Conclusion
Sharif University of Technology
7
Montgomery multiplication algorithm
Montgomery multiplication of Integers
• Define:
z  MM ( x , y )  x yr 1 mod M
• r-1 is the inverse of r mod M:
• r-1r = 1 (mod M)
z  x yr 1 mod M  ( xr )( yr )r 1 mod M
 xyr mod M  zr mod M
Sharif University of Technology
8
Montgomery multiplication algorithm
Montgomery multiplication of Integers
• Example :
1
r  16, r  9 (16 * 9 mod 11  1)
MM (5,7)  5 * 7 * 9 mod 11  7
Sharif University of Technology
9
Montgomery multiplication algorithm
Montgomery multiplication of Integers
• Montgomery multiplication algorithm
• requires no hard division just shifting
Input:
X,Y,M
Output:  =  ,  = 2−
Z = 0
for i = 0 to n-1
Z = Z + xi•Y
if Z is odd then Z = Z + M
Z = Z/2
if Z ≥ M then Z = Z – M
Sharif University of Technology
10
Montgomery multiplication algorithm
Montgomery multiplication of Integers
• Example :
• X = 7 = 0111
• Y = 5 = 0101
• M = 11 = 1011
•
•
•
•
•
Z initially 0
Z = (0 + 5 + 11) / 2 = 8
Z = (8 + 5 + 11) / 2 = 12
Z = (12 + 5 + 11) / 2 = 14
Z = (14 + 0) / 2 = 7 (final result)
Z = 0
for i = 0 to n-1
Z = Z + xi•Y
if Z is odd then Z = Z + M
Z = Z/2
if Z ≥ M then Z = Z – M
Sharif University of Technology
11
Montgomery multiplication algorithm
Montgomery multiplication of Integers
• Conversion using MM
Conversion of integers to/from Montgomery residues with one MM operation
x  MM ( x, r 2 )  xr 2 r 1 mod M  xr mod M
x  MM ( x ,1)  x1r 1 mod M  xr1r 1 mod M  x
Sharif University of Technology
12
Montgomery multiplication algorithm
Montgomery multiplication of Integers
r2
x
X’
1
MM
MM
X’
X
Sharif University of Technology
13
Montgomery multiplication algorithm
Outline

Introduction

Montgomery modular multiplication of integers

Montgomery modular multiplication in GF(2k)

Conclusion
Sharif University of Technology
14
Montgomery multiplication algorithm
Montgomery multiplication in GF(2k)
• Based on polynomial representation
•  ∈  2 is a polynomial of length k and degree less than or equal to  − 1 :
•   =
−1

=0
= −1  −1 + −2  −2 + . . . +1  + 0
• Need an irreducible polynomial of degree
• Instead of computing .  in (2 )
propose to compute . .  −1 in (2 )
Sharif University of Technology
15
Montgomery multiplication algorithm
Montgomery multiplication in GF(2k)
• r : element of the field, presented by the polynomial :    ()
• i.e. if  = ( −1 … 1 0 ), then  = −1 … 1 0
•   =
• very useful in obtaining fast implementations
= 1, then there exist  −1 () and ′  that :
−1  +   ′  = 1
•  −1 () and ′  can be computed using EEA algorithm.(taught in class)
• If gcd   ,
Sharif University of Technology
16
Montgomery multiplication algorithm
Montgomery multiplication in GF(2k)
• Definition:
=      −1   ()
• Can be computed using the following algorithm
Sharif University of Technology
17
Montgomery multiplication algorithm
Montgomery multiplication in GF(2k)
• Algorithm for Montgomery Multiplication
Input :
Output :
Step 1.
Step 2.
Step 3.
,   ,   , ′()
=      −1   ()
=
=   ′   ()
=   +     /()
Sharif University of Technology
18
Montgomery multiplication algorithm
Montgomery multiplication in GF(2k)
• The proposed algorithm is similar to MM of integers
• Only difference : the final subtraction step in the integer case is not
necessary in the polynomial case
• Proof:
deg   ≤ max deg   , deg   + deg   − deg
≤ max 2 − 2,  − 1 +  −
≤−1
• Thus, c(x) is already reduced
Sharif University of Technology
19
Montgomery multiplication algorithm
Montgomery multiplication in GF(2k)
• The modular Mult. and Div. in Step 2, 3 are fast operations
• Since   =
• The remainder operation : simply ignoring the term   ,  ≥
• Div. by   : shifting the polynomial to the right by  places
• Precompute ′() for step 2
• Avoided if the coefficients of () are scanned one bit at a time.
Sharif University of Technology
20
Montgomery multiplication algorithm
Montgomery multiplication in GF(2k)
=      −1   ()
=
• Can be written :
=  −
• Recall :
=  −
−1

=0
()
= −1  −1 +−2  −2 … 1  + 0 ()
Sharif University of Technology
21
Montgomery multiplication algorithm
Montgomery multiplication in GF(2k)
•   =   ()
• Starting from MSB to LSB :
=0
=  − 1  0
=   +
= ()
Sharif University of Technology
22
Montgomery multiplication algorithm
Montgomery multiplication in GF(2k)
•   =   () −
• The shift factor   reverses the direction of summation(LSB to MSB)
=0
= 0   − 1
=   +
= ()/
Sharif University of Technology
23
Montgomery multiplication algorithm
Montgomery multiplication in GF(2k)
Bit-Level Algorithm for Montgomery Multiplication
Input:
,   , ()
Output:   =      −
Step 1.
=0
Step 2.
= 0   − 1
Step 3.
=   +  ()
Step 4.
=   + 0 ()
Step 5.
= ()/
Sharif University of Technology
24
Montgomery multiplication algorithm
Outline

Introduction

Montgomery modular multiplication of integers

Montgomery modular multiplication in GF(2k)

Conclusion
Sharif University of Technology
25
Montgomery multiplication algorithm
Conclusion
• We have described the bit-level algorithm for computing
the product . .  −1 in the (2 )
• The MMM operation would be significantly faster in SW and HW
• Since,
• Division changes to simple shifting
• Remainder operation simply done by ignoring   ,  ≥
• We can speed up more if we use Word-level algorithm for SW
implementation