# Modular Arithmetic Flashcards

*Write a recursive algorithm for multiplication, where x,y are <=n bits long*

What is the running time of mult(x,y)?

O(n^2)

each iteration might have addition on n bits - O(n)

In each iteration we remove one bit so in total we have n iterations. It sums up to O(n^2)

- Write the algorithm for recDivide*
- What is its run-time?*

Recursion depth is O(n)

each iteration takes O(n)

In total - O(n^2)

**Note:** n represents the size of **x**

The size of y does not matter

Describe the substitution rule

Let x,y be in the range 0 to N-1

What is the run-time of computing x+y mod N and x*y mod N?

Since x+y is between 0 and 2(N-1), we might need to substract N from the result. Thus we have addition and substractiom. O(n)

Since x*y is between 0 and (N-1)^2, this product has log((N-1)^2) bits - O(2n). to reach the remainder we need to divide the product by Mod N. in total - O((2n)^2) + O((2n^2)) = O(n^2)

Describe the modular exponentiation algorithm, its run time, and the size of its parameters.

**Describe Euclide’s rule**

**and prove it.**

In order to investigate the run-time of GCD, you need to prove the following lemma:

*If a>=b, then a mod b < a/2*

*Write GCD(a,b)*

Prove the lemma:

If d divides both a and b, and d = ax + by for some integers x and y, then necessarily d = gcd(a,b)

*Write the extension of Euclid’s algorithm*

Prove the lemma:

For any positive integers a and b, the extended Euclid algorithm returns integers x, y, and d such that gcd(a, b) = d = ax + by

Define the multiplicative inverse of *a modulo N.*

- Does it always exist?*
- How many of them can be?*

It may not exist, as for 2 mod 6.

There can be at most 1.

Why ax mod N can be written in the form:

**ax + kN?**

Then, show the gcd(a, N) divides ax mod N

then, show that if gcd(a, N)>1 there can be no multiplicative inverse of a mod N

what happens when gcd(a, N) = 1

Well, that’s how we find the remainder when we compute it in out heads.

Assume we have 13 mod 6 = 1.

We think of the greatest x such that 13>6*x

it is 2. not let’s make it -2 and we have:

13 + -2*6 = 1.

Therefore, ax + kN, can surely be divide by a number **y** which divides both x and N, since ax/**y +** kN/**y** each returns an integer.

Assume:

- gcd(a, N) > 1.
- There exists ax such that ax mod N = 1

we also know that gcd(a,N) divides ax mod N. but no number besides > 1 divides 1. contradiction.

If gcd(a, N) = 1, by the lemma we have ax + Ny = 1. which means that ax mod N = 1. thus x is the multiplicative inverse of a mod N.

*Explain what it means for a and N to be relatively prime.*

gcd(a, N) = 1