Week 8 - Modular Arithmetic

First lets remind ourselves of the definition of modular arithmetic.

Modular arithmetic

Modular arithmetic

Given two values (though this can be expanded to other domains). We define modulo to be the remainder when dividing by . Write Then or equally (mod ).

Theory

Mod a given integer is an equivalence relation on and the concept expands more generally to other domains.

Link to original

Within a computers architecture as numbers are stored in binary calculating mod is simple as taking the least significant bits. Therefore it is quite cheap. However, when the value is not it can get harder.

Exponent problem

Statement

Modular exponent problem

Given 3 -bit integers what is mod .

Link to original

This is the problem we want to solve in the next step. We would like an algorithm that is linear in which would be the input size. Note that , and are all bounded by so if this appears in our bound we will be exponential.

It is quite easy to calculate (mod ) as you recursively calculate (mod ). Using this idea we get a first attempt at solving the above problem.

Modular exponent algorithm

Modular exponent algorithm

This algorithm has a polynomial run time in the size of the input to calculate powers in using modular arithmetic. This has not been sped up using Euler’s theorem (modular arithmetic).

Algorithm

resursive_mod_exp(x,y,N):
	Input: n-bit integers x,y,N >= 0
	Ouput: x^y mod N
1. if y = 0, return 1
2. z = resursive_mod_exp(x, floor(y/2), N)
3. if y is even return z^2 mod N
4. if y is off return xz^2 mod N

Run time

The algorithm runs for at most loops as is an -bit integer. Calculating multiplication of -bit integers takes . Therefore this algorithm runs in time.

Correctness

This derives from basic properties of modular arithmetic.

Link to original

Multiplicative inverse problem

Modular multiplicative inverses

The multiplicative inverse of mod is such that .

This may not exist if is not prime.

Modular multiplicative inverse existence

Statement

Lemma

For there exists where such that (mod ) if and only if .

Proof

Let the greatest common divisor be , so and where . Therefore consider the following modular arithmetic As has an inverse consider

Link to original

Though knowing an inverse exists isn’t helpful algorithmically.

Statement

Modular inverse problem

Given 2 -bit integers what is mod .

Link to original

Let’s first look at a helpful rule for finding this.

Euclid's rule

Statement

Euclid's rule

For integers where we have

Proof

We prove more generally that which will give the desired result from the definition of modular arithmetic.

Note that if () and () then ().

Also if () and () then ()).

Therefore both sides share divisors and so the greatest common divisor.

Link to original

We can use this rule to calculate greatest common divisors.

Euclidean algorithm

Euclidean algorithm

This algorithm is used to calculate the greatest common divisor for two positive integers. This uses Euclid’s rule and modular arithmetic.

Algorithm

Euclid(x,y):
	Input: integers x,y where x >= y >= 0
	Output: gcd(x,y)
1. If y = 0 return x
2. return Eculid(y, x mod y)

Run time

If and are -bit integers then calculating mod takes time. From Claim 1 we have every 2 rounds decreases by at least a factor of 2. So there are at most rounds giving this algorithm a run time of .

Claim 1

Claim 1

If then mod < .

Proof

If then mod .

If then mod = .

Correctness

This follows from Euclid’s rule.

Link to original

Moreover we can extend this to calculate the inverse.

Extended Euclidean algorithm

Extended Euclidean algorithm

This algorithm extends the Euclidean algorithm to be able to calculate the greatest common divisor of two integers.

Algorithm

extended_euclidean(x,y):
	Input: integers x, y where x >= y >= 0
	Output: integers d, a, b where d = gcd(x,y) and d = xa + yb
1. if y = 0, return (x,1,0)
2. (d, a', b') = extended_euclidean(y,x mod y)
3. return (d, b', a' - floor(x/y)b')

Runtime

Notice this is functionally the same as Euclidean algorithm. So if are -bit integers then this takes .

Correctness

The fact that is correct follows from Euclid’s rule.

We proceed by induction on .

If then and we are done.

Suppose we have it true for all and we want to check it is correct for .

We run extended_euclidean(y,x mod y) lets set mod as we get back correct such that and .

Now write where . Then calculate

Link to original

Example

To compute mod we run the Extended Euclidean algorithm on and .

x	y	c	a	b
360	7	51	-2	103
7	3	2	1	-2
3	1	3	0	1
1	0	-	1	0

First calculate the , and columns going downwards. Where with .

Second calculate and starting form the bottom where and . Note .

Then as we have that mod .