Week 9: Number Theory Flashcards
division
- 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
notation of division
- “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)
division - theorem 1 (3 things)
- 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
proof for part a of theorem 1: if a | b and a |c, then a | (b + c)
proof for part b of theorem 1: if a | b and a |bc for all integers c
proof for part c of theorem 1: if a | b and b | c, then a | c
the division algorithm
- 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
modular arithmetic
- 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)
modular exponentiation
- can apply modular arithmetic rules on exponents
- break down the exponent according to binary
- review with videos/something to understand
fast modular exponentiation
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
primes
- 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…
composite
- term for a number that is not prime
fundamental theorem of arithmetics
primes - theorem 1
primes - lemma 2
sieve of eratosthenes
- 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
greatest common divisors
- the largest divisor that divides both m and n is called the greatest common divisor of m and m
- denoted as gcd(m, n)
euclidean algorithm
- Let a = bq + r, where a, b, q, and r are integers
- Suppose x ∣ a and x ∣ b, then x ∣ r (since r = a – bq)
- any common divisor of a and b is also a common divisor of b and r
2) Suppose y ∣ b and y∣ r, then y | a (since a = bq + r) - any common divisor of b and r is also a common divisor of a and b
- then gcd(a,b) = gcd(b, r)
euclidean algorithm implementation
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)
bezout’s theorem
hasing functions
- 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)
pseudo random number generator
classical cryptography
caeser cipher
the encryption function
the decryption function
the RSA cryptosystem
preparation of public and private keys in RSA
mathematics behind RSA - inverse modulo N
the Chinese remainder theorem
Fermat’s little theorem
properties of modular arithmetic (4 things)
- 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
relatively prime
- integer of a and b are relatively prime if their greatest common divisor is 1
- ex. gcd(25, 36) = 1
