Week 9: Number Theory

Question 1

division

Answer 1

• let a and b be two integers with a not equal to 0
• we say that a divides b if there is an integer k such that b = ka
• we write a | b if a divides b

Question 2

notation of division

Answer 2

• “a divides b” is denoted by a | b (ex. 3 | 21)
• 3 is a factor of 21, 3 is a divisor of 21, 21 is a multiple of 3
• “a does not divide b” is denoted by a ∤b (| with slash in it) (ex. 3 ∤ 20)

Question 3

division - theorem 1 (3 things)

Answer 3

• let a, b, c be integers where a is not equal to 0
• if a ∣ b and a ∣ c, then a ∣ (b + c)
• If a ∣ b, then a ∣ bc for all integers c
• If a ∣ b and b ∣ c, then a ∣ c

Question 4

proof for part a of theorem 1: if a | b and a |c, then a | (b + c)

Answer 4

• a | b means b = ma for some integer m
• a | c means c = na for some integer n
• b + c = (m + n ) a, thus a | (b+c)

Question 5

proof for part b of theorem 1: if a | b and a |bc for all integers c

Answer 5

• a | b means b = ma for some integer m
• bc = (mc)a, mc is an integer
• thus a | bc

Question 6

proof for part c of theorem 1: if a | b and b | c, then a | c

Answer 6

• a | b means b = ma for some integer m
• b | c means c = nb for some integer n
• c = nb = (nm)a, thus a | c.

Question 7

the division algorithm

Answer 7

• let a be an integer and d a POSITIVE integer
• then there are unique ints q and r with 0 ≤ r < d, such that a = dq + r
• a is dividend, d divisor, q quotient, r remainder
• notation: q = a div d, r = a mod d

Question 8

modular arithmetic

Answer 8

• let a and b be integer and M is a positive integer
• say that a is congruent to b modulo M if M divides a - b
• we shall write a ≡ b (mod M) if and only if M | (a – b)

Question 9

modular exponentiation

Answer 9

• can apply modular arithmetic rules on exponents
• break down the exponent according to binary
• review with videos/something to understand

Question 10

fast modular exponentiation

Answer 10

procedure modular_exp(b, n = 𝑎𝑘−1𝑎𝑘−2 … 𝑎1𝑎0 2 , m):
# 𝑎𝑘−1𝑎𝑘−2 … 𝑎1𝑎0 2 is the binary representation of n
x = 1
power = b % m
for i = 0 to (k-1)
if a[i] == 1
then x := (x * power) % m
power := (power * power) % m
return x
#x equals 𝑏𝑛 𝑚𝑜𝑑 𝑚
12

Question 11

primes

Answer 11

• a prime number p is an integer greater than 1 that is divisible ONLY by one and itself
• there are an infinite number of prime number
• ex. 2, 3, 5, 7, 11, 13…

Question 12

composite

Answer 12

• term for a number that is not prime

Question 13

fundamental theorem of arithmetics

Answer 13

• Every positive integer can be written as the product of primes where the prime factors are written in order of
  increasing size
  -if n is a natural numbers and p1 < p2 < ⋯ < pm are distinct primes, then
• n = p1^(e1) ⋅ p2^(e2) ⋯ pm^(em)

Question 14

primes - theorem to determine if number is composite

Answer 14

If 𝑛 is a composite integer, then n has a prime divisor less than or equal to √𝑛.

Question 15

sieve of eratosthenes

Answer 15

• used to find all primes not exceeding a specified positive integer
• can write out all the numbers, go number by number, and remove anything that is divisible by that number
• will be left with prime numbers
• can be implemented with code

Question 16

greatest common divisors

Answer 16

• the largest divisor that divides both m and n is called the greatest common divisor of m and m
• denoted as gcd(m, n)

Question 17

euclidean algorithm

Answer 17

-Let a = bq + r, where a, b, q, and r are integers
-Then gcd(a,b) = gcd(b, r)

Question 18

euclidean algorithm implementation

Answer 18

procedure gcd (a, b: positive integers):
x := a
y := b
while y > 0
r := x mod y
x := y
y := r
return x
# x equals to gcd(a, b)

Question 19

bezout’s theorem

Answer 19

• If a and b are positive integers, then there exist integers s and t such that gcd(a, b) = sa + tb.
• gcd(a, b) can be expressed as a linear combination of a and b

Question 20

hashing functions

Answer 20

• one needs a fast method of locating a given record in a huge set of records
• hashing is a possible solution, where every record has a unique key k, and a hashing function h(k) maps the set of keys into the available memory locations
• most common function is
  h(k) = k mod M (M is memory size)

Question 21

pseudo random number generator

Question 22

classical cryptography

Question 23

caeser cipher

Answer 23

• encrypting a message by a certain shift
• ex. shifting 3 letters forward
  B -> E, Z -> C

Question 24

the encryption function

Answer 24

encrypt(c) = (c + 3) mod 26
- shift is 3 in this example
- codes the message

Question 25

the decryption function

Answer 25

decrypt(c) = (c – 3) mod 26 - shifts back 3 in this example - decodes the message

Question 26

the RSA cryptosystem

Answer 26

- the most widely used public key cryptosystem - public key cryptosystems made it practical to send encrypted messages between parties ex. seller and buyer

Question 27

preparation of public and private keys in RSA

Answer 27

- two prime numbers, p and q - computes N = p*q and φ = (p-1)(q-1) - finds an integer e such that gcd(e, φ) = 1 - computes d, the multiplicative inverse of e mod φ: (e * d mod φ) = 1 - public key is N and e, private key is d

Question 28

the Chinese remainder theorem

Question 29

Fermat's little theorem

Answer 29

If p is a prime number and m is an integer not divisible by p, then m^(p-1) ≡ 1 mod p Or equivalently m^p ≡ m mod p

Question 30

rules of modular arithmetic (5 things)

Answer 30

- If a ≡ b (mod M) and c ≡ d (mod M) - a + c ≡ b + d (mod M) - ac ≡ bd (mod M) - (a + b) mod M = ((a mod M) + (b mod M)) mod M - (ab) mod M = ((a mod M) x (b mod M)) mod M

Question 31

relatively prime

Answer 31

- integer of a and b are relatively prime if their greatest common divisor is 1 - ex. gcd(25, 36) = 1

Question 32

modular arithmetic and congruency

Answer 32

- a and b are integers, M is a positive integer - a is congruent to b modulo M if M divides a - b - statement: a = b (mod M) iff M | (a - b)

Question 33

modular arithmetic addition/multiplication rule with a, b, c, d

Answer 33

- a = b (mod M) and c = d (mod M) 1.) a + c = b + d (mod M) 2.) ac ≡ bd (mod M)

Question 34

modular arithmetic addition/multiplication rule with a, b

Answer 34

Let M be a positive integer; and let a and b be integers. Then (a + b) mod M = ((a mod M) + (b mod M)) mod M (ab) mod M = ((a mod M) x (b mod M)) mod M

Question 35

how many prime numbers are there

Answer 35

infinitely many

Question 36

public key and private key formulas

Answer 36

- Public key: N and e C = encrypt(M) = M^e (mod N) - Private key: d M = decrypt(C) = C ^ d (mod N)

Question 37

inverse modulo N

Answer 37

b is an inverse of a modulo N if b* a ≡ 1 mod N

Question 38

theorem for inverse modulo N

Answer 38

- m > 1 and gcd(m, n) = 1 (i.e., m and n are relatively prime), then an inverse of n modulo m exists and it is - equal to s in the following equation: s x n + t x m = 1 - can be found efficiently by the extended Euclidean algorithm