# Modular Arithmetic Flashcards

1
Q

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

A
2
Q

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

A

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)

3
Q
• Write the algorithm for recDivide*
• What is its run-time?*
A

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

4
Q

Describe the substitution rule

A
5
Q

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?

A

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)

6
Q

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

A
7
Q

Describe Euclide’s rule

and prove it.

A
8
Q

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

A
9
Q

Write GCD(a,b)

A
10
Q

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)

A
11
Q

Write the extension of Euclid’s algorithm

A
12
Q

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

A
13
Q

Define the multiplicative inverse of a modulo N.

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

It may not exist, as for 2 mod 6.

There can be at most 1.

14
Q

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

A

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.

15
Q

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

A

gcd(a, N) = 1

16
Q

recall the modular division theorem

How does it help?

A

This resolves the issue of modular division:

when working modulo N, we can divide by numbers relatively prime to N - and only by these. That is, if we have:

x*z = x*w (mod N)

we can divide by x to have:

z = w (mod N)

only if x is relatively prime to N.

17
Q

Describe and prove Fermat’s little theorem

A
18
Q

what is the assumption behind the Miller-Rabin algorithm

A

If N is prime, there are only two solutions for x^2(modN) = 1

which are, 1 and N-1.

19
Q

N-1 = 2^s * t

define a, a testimony of N.

A
20
Q

Write the Miller-Rabin algorithm

A
21
Q
A
22
Q

Analyze the following

A
23
Q

Write the improve algorithm for primality

A
24
Q

Write Lagrange’s prime number theorem and desribe the algorithm for finding a random n-bit prime number

In addition explain why checking only for a = 2,3,5 is enough

A

It is enough to check for a = 2,3,5 because the numbers are chosen randomly. If it wasn’t and an adversary might look for the specific case in which it fails.

25
Q

RSA Scheme:

How should we perceive the messages from Alice to Bob?

A
26
Q

If N is composite, of the naturals <n></n>

<div>
<div> </div>
</div>

</n>

A

at least 3/4

27
Q
A