5 Modular Arithmetic

Dr Kulothungan

Learning Objectives

➢   To understand the basics of Modular Arithmetic

➢   To learn about the binary operation

➢   To learn about the additive and multiplicative inverse

➢   Some examples related to these concepts

6.1 INTRODUCTION

Modular arithmetic is a system of arithmetic for integers, where numbers “wrap around” upon reaching a certain value. Modular arithmetic allows us to easily create groups, rings and fields which are fundamental building blocks of most modern public-key cryptosystems.

For example, Diffie-Hellman uses the multiplicative group of integers modulo a prime pp. There are other groups which would work.Modular or clock arithmetic is arithmetic on a circle instead of a number line modulo N , we use only the twelve whole numbers from 0 through N-1

1:00 and and 13:00 hours are the same(1=13mod12)

1:00 and and 25:00 hours are the same(1=25mod12)

6.1.1 Usage of Modular Arithmetic

Modular arithmetic is very well understood in terms of algorithms for various basic operations. That is one of thereason why we use finite fields (AES) in symmetric key cryptography. Cryptography requires hard problems. Some problems become hard with modular arithmetic. For example, logarithms are easy to compute over all integers . but can become hard to compute when you introduce a modular reduction. Similarly with finding roots. Mod-arithmetic is the central mathematical concept in cryptography. Almost any cipher from the Caesar Cipher to the RSA Cipher use it.There are two types of “mod”.

The mod function

▪      Inputs a number a and a base b

▪      Outputs a mod b a number between 0 and b –1 inclusive

▪      This is the remainder of a b

▪      Similar to Java’s % operator.

▪      Relates two numbers a, a’ to each other relative some base b

▪      a a’ (mod b) means that a and a’ have the same remainder when dividing by b

Similar to Java’s “%” operator except that answer is always positive. E.G. -10 mod 3 = 2, but in Java –10%3 = -1.

Q:     Compute

1.      113 mod 24

2.      -29 mod 7

6.2 Congruent numbers

Integers that leave the same remainder when divided by the modulus m are somehow similar, however, not identical. Such numbers are called “congruent”. For instance, 1 and 13 and 25 and 37 are congruent mod 12 since they all leave the same remainder when divided by 12.

Equivalently: a mod b = a’ mod b

Q:     Which of the following are true?

1.      3   3 (mod 17)

2.      3   -3 (mod 17)

3.      172   177 (mod 5)

4.      -13   13 (mod 26)

A:

1.      3 3 (mod 17) True. any number is congruent to itself (3-3 = 0, divisible by all)

2.      3   -3 (mod 17) False. (3-(-3)) = 6 isn’t divisible by 17.

3.      172   177 (mod 5) True. 172-177 = -5 is a multiple of 5

4.      -13   13 (mod 26) True: -13-13 = -26 divisible by 26.

The (mod) congruence is useful for manipulating expressions involving the mod function. It lets us view modular arithmetic relative a fixed base, as creating a number system inside of which all the calculations can be carried out.

•      a mod b   a (mod b)

•      Suppose a   a’ (mod b) and c   c’ (mod b) Then:

    –  a+c    (a’+c’ )(mod b)

–  ac   a’c’ (mod b)

–  a k    a’ k (mod b)

6.3Modular Addition

First add the two numbers, Secondly, divide the sum by the modulus to compute the remainder. In “8-hour-land” where a day lasts only 8 hours, we would add 12 and 9 as follows: First, 12+9 = 21, secondly 21 divided by the modulus 8 leaves a remainder of 5 since 21=2*8+5.

6.4 Modular Subtraction

First subtract, secondly compute the remainder. Example 1: 25 – 8 = 17 MOD 12 = 5

Example 2: 50 – 11 = 39 MOD 12 = 3

6.5 Modular Multiplication

A mod expert would find the answer to 123 * 62 mod 12 immediately. It is 6.Without being a Gauss genius, she computes 123 mod 12 = 3 and 62 mod 12 = 2 and multiplies those two answers. To verify this: 123*62 mod 12 = 7626 mod 12 = 6. This computation aid is true for addition and subtraction as well

6.6 Computation Rules for Mod Arithmetic

    ● a + b mod m = (a mod m) + (b mod m)

● a – b mod m = (a mod m) – (b mod m)

● a * b mod m = (a mod m) * (b mod m)

Example 1: Addition Modulo 8

Example 3: Additive and Multiplicative inverses Modulo 7

  6.7 Properties of Modular Arithmetic

6.8 Modular Arithmetic Examples

Q:     Compute the following.

1.      307¹⁰⁰¹ mod 102

2.      (-45 · 77) mod 17

3.       

 

 Therefore, the answer is 0.

6.9 Proving Modular Identities

6.10 Simple Encryption and Decryption using Modular Arithmetic

6.10.1 Basic Steps involved in Encryption

Variations on the following have been used to encrypt messages for thousands of years.

1.      Convert a message to capitals.

2.      Think of each letter as a number between 1 and 26.

3.      Apply an invertible modular function to each number.

4.   Convert back to letters (0 becomes 26).

6.10.2 Encryption Example

Let the encryption function be

f  (a) = (3a + 9) mod 26

Encrypt “Stop Thief”

1. STOP THIEF  (capitals)

2. 19,20,15,16 20,8,9,5,6

3. 14,17,2,5 17,7,10,24,1

4. NQBE QGJXA

6.10.3 Decryption Example

Decryption works the same, except that you apply the inverse function.

Example: Find the inverse of

f (a) = (3a + 9) mod 26

g (a) = 3-1 (a – 9)

We’ll see that since gcd(3,26) = 1, the inverse of 3 is actually well defined modulo 26 and is the number 9. This gives:

g (a) = 9 (a – 9) mod 26 = (9a – 3) mod 26

Summary

➢ The basics of Modular Arithmetic is explored

➢ The Modular arithmetic operation is explored