Module NumberTheoryBasics

Basic Number Theory for RSA Algorithm
Dr. Natarajan Meghanathan

Assistant Professor of Computer Science Jackson State University, Jackson MS
E-mail: natarajan.meghanathan@jsums.edu
Modular Arithmetic
Given any positive integer n and any integer a, if we divide a by n, we get a quotient q and a remainder r that obey the following relationship:
a = q * n + r, 0 r < n and r is the remainder, q is the quotient When a is positive 0 1 2 n 2n 3n (q-1)n qn r n (q)n r Example:
a = 59; n = 7; 59 = (8)*7 + 3 a = -59; n = 7; -59 = (-9)*7 + 4 59 mod 7 = 3 -59 mod 7 = 4 r = 3; q = 8 r = 4; q = -9
n a (q+1)n
When a is negative (q-1)n 3n 2n n 2 1 0
All the numbers marked on the line are actually negative with respect to sign
Modular Arithmetic
Two integers a and b are said to be congruent modulo n, if a mod n = b mod n. This is written as a b mod n.
We say a and b are equivalent to each other in class modulo n
Example:
73 4 mod 23, because 73 mod 23 = 4 = 4 mod 23 21 -9 mod 10, because 21 mod 10 = 1 = -9 mod 10
Properties of the Modulo Operator

If a b mod n, then (a b) mod n = 0 If a b mod n, then b a mod n If a b mod n and b c mod n, then a c mod n
Example:
73 4 mod 23, then (73 4) mod 23 = 0 73 4 mod 23, then 4 73 mod 23, because 4 mod 23 = 73 mod 23 73 4 mod 23 and 4 96 mod 23, then 73 96 mod 23.
Modular Arithmetic
Now, that we have studied the meaning of equivalency or congruent modulo n, it is see that the mod n operator maps all integers (negative and positive) into the set of integers [0, 1, ., n1]. Example: Class of modulo 15
From the above table, we could say things like -38 22 mod 15 24 54 mod 15 -38 mod 15 = 7 [-38 = (-3)*15 + 7] 24 mod 15 = 9 [24 = (1)*15 + 9] 22 mod 15 = 7 [22 = (1)*15 + 7] 54 mod 15 = 9 [54 = (3)*15 + 9]
Modular Arithmetic
Properties:
(x + y) mod n = (x mod n + y mod n) mod n Example:
Compute: (54 + 49) mod 15 (54 + 49) mod 15 = 103 mod 15 = 13 54 mod 15 = 9 49 mod 15 = 4 (54 mod 15 + 49 mod 15) = 9 + 4 = 13 (54 mod 15 + 49 mod 15) mod 15 = 13 mod 15 = 13
Example:
Compute (42 + 52) mod 15 (42 + 52) mod 15 = 94 mod 15 = 4 42 mod 15 = 12 52 mod 15 = 7 (42 mod 15 + 52 mod 15) = 12 + 7 = 19 (42 mod 15 + 52 mod 15) mod 15 = 19 mod 15 = 4
Modular Arithmetic
Properties:
(x * y) mod n = (x mod n * y mod n) mod n Example:
Compute: (54 * 49) mod 15 (54 * 49) mod 15 = 2646 mod 15 = 6 54 mod 15 = 9 49 mod 15 = 4 (54 mod 15 * 49 mod 15) = 9 * 4 = 36 (54 mod 15 * 49 mod 15) mod 15 = 36 mod 15 = 6
Example:
Compute (42 * 52) mod 15 (42 * 52) mod 15 = 2184 mod 15 = 9 42 mod 15 = 12 52 mod 15 = 7 (42 mod 15 * 52 mod 15) = 12 * 7 = 84 (42 mod 15 * 52 mod 15) mod 15 = 84 mod 15 = 9
Modular Arithmetic
Properties:
(a * b * c) mod n = ( (a mod n) * (b mod n) * (c mod n) ) mod n
(a * b * c) mod n = ( ( ( (a mod n) * (b mod n) ) mod n ) * (c mod n) ) mod n
(a * b * c * d) mod n = ( (a mod n) * (b mod n) * (c mod n) * (d mod n) ) mod n Similarly, (a * b * c * d * e) mod n. Example:

Compute (42 * 56 * 98 * 108) mod 15 Straightforward approach: (42 * 56 * 98 * 108) mod 15 = (234893568) mod 15 = 3 Optimum approach 1 Optimum approach 2
Modular Arithmetic
Modular Exponentiation
The Right-to-Left Binary Algorithm
Example for Modular Exponentiation

To compute 541 mod 9
Straightforward approach:
541 mod 9 = (45474735088646411895751953125) mod 9 = 2 Number of multiplications - 40
Using the Right-to-Left Binary Algorithm

Write 41 in binary: 101001 541 = 532 * 58 * 51 541 mod 9 = (532 * 58 * 51) mod 9
Example for Modular Exponentiation

To compute 361 mod 8
Straightforward approach:
361 mod 8 = (12717347825648619542883299603) mod 8 = 3 Number of multiplications - 60
Using the Right-to-Left Binary Algorithm

Write 61 in binary: 111101 341 = 332 * 316 * 38 * 34 * 31 541 mod 9 = (532 * 58 * 51) mod 9
Multiplicative Inverse Modulo n

If (a * b) modulo n = 1, then
a is said to be the multiplicative inverse of b in class modulo n b is said to be the multiplicative inverse of a in class modulo n
Example:
Find the multiplicative inverse of 7 in class modulo 15 Straightforward approach:
Multiply 7 with all the integers [0, 1, , 14] in class modulo 15 There will be only one integer x for which (7*x) modulo 15 = 1
Find the multiplicative inverse of 9 in class modulo 13

Multiply 9 with all the integers [0, 1, , 12] in class modulo 13 There will be only one integer x for which (9*x) modulo 13 = 1
A more efficient approach to find multiplicative inverse in class modulo n is to use the Extended Euclid Algorithm
Euclids Algorithm to find the GCD

Given two integers m and n (say m > n), then
GCD (m, n) = GCD (n, m mod n) One can continue using the above recursion until the second term becomes 0. The GCD (m, n) will be then the value of the first term, because GCD (k, 0) = k
Example: GCD (120, 45)

GCD (120, 45) = GCD (45, 30) = GCD (30, 15) = GCD (15, 0) = 15

GCD (45, 12) = GCD (12, 9) = GCD (9, 3) = GCD (3, 0) = 3

GCD (53, 30) = GCD (30, 23) = GCD (23, 7) = GCD (7, 2) = GCD (2, 1) = GCD (1, 0) = 1
Note: Two numbers m and n are said to be relatively prime if

GCD (m, n) = 1.
Property of GCD
For any two integers m and n,
We can write m * x + n * y = GCD (m, n)
x and y are also integers We find x and y through the Extended Euclid algorithm
If m and n are relatively prime, then

there exists two integers x and y such that m * x + n * y = 1
x is the multiplicative inverse of m modulo n y is the multiplicative inverse of n modulo m We could find x and y through the Extended Euclid algorithm
Extended Euclid Algorithm

Theorem Statement
Let m and n be positive integers. Define
a[0] = m, a[1] = n x[0] = 1, x[1] = 0, y[0] = 0, y[1] = 1, q[k] = Floor( a[k-1]/ a[k]) for k > 0 a[k] = a[k-2] (a[k-1]*q[k-1]) for k > 1 x[k] = x[k-2] (q[k-1] * x[k-1]) for k > 1 y[k] = y[k-2] (q[k-1] * y[k-1]) for k > 1
If a[p] is the last non-zero a[k], then

a[p] = GCD (m, n) = x[p] * m + y[p] * n x[p] is the multiplicative inverse of m modulo n y[p] is the multiplicative inverse of n modulo m
Example for Extended Euclid Algorithm

Find the multiplicative inverse of 30 modulo 53
The larger of the two numbers is our m and the smaller is n Initial Setup of the computation table We want to find the x and y m such that 53x + 30y = 1 n
Iteration 1
Iteration 2

Iteration 3
Iteration 4
Iteration 5
-13*53+30*23 = 1 = GCD
23 is the multiplicative inverse of 30 modulo 53 -13 17 is the Multiplicative inverse of 53 modulo 30
STOP!

Find the multiplicative inverse of 17 modulo 89
The larger of the two numbers is our m and the smaller is n Initial Setup of the computation table We want to find the x and y m such that 89x + 17y = 1 n
Iteration 1
Iteration 2

Iteration 3
STOP! -4*89 + 21*17 = 1 = GCD

21 is the multiplicative inverse of 17 modulo 89
- 4 13 is the multiplicative inverse of 89 modulo 17

Module NumberTheoryBasics

Uploaded by

Copyright:

Available Formats

Module NumberTheoryBasics

Uploaded by

Document Information

Original Description:

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Module NumberTheoryBasics

Uploaded by

Copyright:

Available Formats

Basic Number Theory for RSA Algorithm

Dr. Natarajan Meghanathan

When a is negative (q-1)n 3n 2n n 2 1 0

Properties of the Modulo Operator

(a * b * c * d) mod n = ( (a mod n) * (b mod n) * (c mod n) * (d mod n) ) mod n Similarly, (a * b * c * d * e) mod n. Example:

Example for Modular Exponentiation

Using the Right-to-Left Binary Algorithm

Example for Modular Exponentiation

Using the Right-to-Left Binary Algorithm

Multiplicative Inverse Modulo n

Find the multiplicative inverse of 9 in class modulo 13

Euclids Algorithm to find the GCD

Example: GCD (120, 45)

Example: GCD (45, 12)

Example: GCD (53, 30)

Note: Two numbers m and n are said to be relatively prime if

If m and n are relatively prime, then

Extended Euclid Algorithm

If a[p] is the last non-zero a[k], then

Example for Extended Euclid Algorithm

Example for Extended Euclid Algorithm

Example for Extended Euclid Algorithm

Example for Extended Euclid Algorithm

STOP! -4*89 + 21*17 = 1 = GCD

- 4 13 is the multiplicative inverse of 89 modulo 17

You might also like

STOP! -489 + 2117 = 1 = GCD