L3 (Algs with Numbers)

Question 1

Two important problems with numbers are Factoring and Primality. What is the premise of these problems?

Answer 1

Factoring: Given a number N, express it as a product of prime factors
Primality: Given a number N, determine whether it is a prime

Question 2

What is the time complexity of the fastest known factoring algorithm?

Answer 2

The fastest known algorithm for factoring is exponential in the number of bits N, O(2^n)

Question 3

Consider the standard “algorithm” for adding binary numbers (addition) x and y with these numbers being n bits long

What is the runtime of this algorithm?

Answer 3

The runtime is O(n) to add x and y

Note: For computers, 32 or 64 bit addition is constant time via an ALU

Question 4

Consider the multiply(x,y) algorithm

If n is the number of bits in x and y, What is the runtime of this algorithm using the naive approach (no FFT or multiDC)?

Answer 4

The runtime is O(n^2)

This algorithm can run recursively

Question 5

Describe the multiply(x, y) algorithm for multiplying numbers x and y

What is the base case?

Answer 5

x * y = {
2 * (x * floor(y/2)) : if y is even
x + 2 * (x * floor(y/2)): if y is odd
}

The base case is if y = 0

Question 6

For an algorithm to divide an integer x by an integer y != 0, we have to find two numbers. What are they?

Answer 6

Find:
1. find a quotient q
2. find a remainder r < y

Such that x = q * y + r

Question 7

What is the formal rule for x modulo N?

Answer 7

Given integers x and N, we write x = qN + r where 0 <= r < N is the remainder and then

x mod N = r

Question 8

If the modulo can be thought of as a function. What would the inputs and outputs be?

Answer 8

inputs: integers x and N
outputs: r = the remainder of x divided by N

Question 9

What does it mean for two numbers to be congruent?

Answer 9

Two numbers (x and y) are congruent (or equivalent) if they have the name remainder when divided by N. We write:

x ≡ y (mod N)

Which also means x mod N = y mod N

Question 10

Congruency states that two numbers have the same remainder:

x ≡ y (mod N)

What can we say about what N divides?

Answer 10

If x and y are congruent, then we can say that N divides (x - y) with no remainder

Question 11

Congruent numbers have a substitution property. If we have:
x ≡ x’ (mod N) and
y ≡ y’ (mod N)

then what can we say?

Answer 11

If x ≡ x’ (mod N) and
y ≡ y’ (mod N)

Then
x + y ≡ x’ + y’ (mod N)
and
x*y ≡ x’y’ (mod N)

That is, if (x, x’) are congruent and (y, y’) are congruent then:

• x + y is congruent to x’ + y’
• xy is congruent to x’y’

Question 12

What are the modulo arithmetic properties for:
- Associativity
- Commutativity
- Distributivity

Answer 12

Associativity:
x + (y + z) ≡ (x + y) + z (mod N)

Commutativity:
xy ≡ yx (mod N)

Distributivity:
x(y+z) ≡ xy + y*z (mod N)

ie: The following pairs are congruent:
[x+(y+z), (x+y)+z]
[xy, yx]
[x(y+z), xy+y*z]

Question 13

Consider two modulo N numbers x and y. Since each number is less than N, the number of bits is n <= log2 (N)

What is the time complexity of:
- Modulo Addition
- Modulo Multiplication

Answer 13

• Modulo Addition: O(n) time
• Modulo Multiplication: O(n^2) time