Walk Through of RSA Public-key Encryption for Beginners - Part II: Some Background on Modular Arithmetics


We will have a simple background review of modular arithmetic. It will consist of two concepts. 1.What is modular arithmetic. 2. Inverse modular arithmetic.

1. What is modular arithmetic.

Simplely put, just think of remainders.

10/3=3 remainder means 10mod3=1. 23/4=5 remainder 3 means 23mod4=5

In a more mathatical terms, x=y mod m means  (x-y) divides m.

2. Modular Multiplicative Inverse 

Again, think about  elementary arithmetic. The multiplicative inverse of x is 1/x, because x*1/x=1

In modular arithmetic, multiplicative inverse is defined by 

If x is the multiplicative inverse of a mod m, then ax =1mod m, in other words, (ax-1) divides m.

a has a multicative inverse if gcd (a, m)=1, (gcd stands for greatest common divisor, gcd(a,m) =1 mean a and m are relatively prime to each other)

I would like to think about it this way, a * ? = (a multiple of m) +1

For example, what is the multiplicative inverse of 4 mod 27 ? 

4 * ? = (a multiple of 27) +1

4 * 7 = 1*27 +1

so 4^-1 mod 27 = 7

 

« Resolve elem is null in classie.js Walk through of RSA public-key encryption for beginners - Part III:Bijection functions »