Integers, Division, Primes and Composites

Integers and Division

• Number theory explores integers and their properties
• Z represents the set of integers {..., -2, -1, 0, 1, 2, ...}
• Z+ represents the set of positive integers {1, 2, ...}
• Number theory finds applications in computer science, such as indexing, encryption, error correction, and random number generation

Division

• For integers a and b (a ≠ 0), a divides b if there exists an integer c such that b = ac
• If a divides b, then a is a factor of b, and b is a multiple of a
• The notation a | b signifies that a divides b

Divisibility Properties

• If a, b, and c are integers, then
  • 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

Primes and Composites

• A prime number is a positive integer greater than 1, divisible only by 1 and itself
  • Examples of primes include: 2, 3, 5, 7, 11, 13, etc.
• A composite number is a positive integer greater than 1 that is not prime.
  • Examples of composite numbers include: 4, 6, 8, 9, etc.

Fundamental Theorem of Arithmetic

• Any positive integer greater than 1 can be expressed as a product of prime numbers
  • Factorization is the process of finding these prime factors

Factorization of Composites into Primes

• Examples include:
  • 100 = 2 * 2 * 5 * 5 = 2² * 5²
  • 99 = 3 * 3 * 11 = 3² * 11

Primality Testing

• Simple Approach 1: Test if any number x < n divides n; if so, n is composite
• Approach 2: Test if any prime x < n divides n; if so, n is composite.
  • If n is relatively small, this test is good because we can enumerate (memorize) all small primes
  • If n is large there can be larger not obvious primes

Theorem for Primality Testing

• If n is a composite number, then n has a prime divisor less than or equal to √n
• Approach 3: to test its primality, test if any prime number x < √n divides it

Number of Primes

• There are infinitely many primes
• Proof by Euclid: Assume a finite number of primes, p1, p2, ..., pn; then Q = p1p2...pn + 1 is not divisible by any of these primes, a contradiction

Division with Remainder

• For an integer a and a positive integer d, there are unique integers q and r with 0 ≤ r < d such that a = dq + r
  • a is the dividend, d the divisor, q the quotient, and r the remainder
  • q = a div d, r = a mod d

Greatest Common Divisor (GCD)

• For integers a and b, not both 0, the largest integer d such that d | a and d | b is the greatest common divisor, denoted gcd(a, b)
• Factoring can find the GCD by factoring a and b into their prime factorizations: a=p1^a1 * p2^a2 * p3^a3 ... pk^ak and b = p1^b1 * p2^b2 * p3^b3 ... pk^bk, then: gcd(a,b) = p1^min(a1,b1) * p2^min(a2,b2) * p3^min(a3,b3) ... pk^min(ak,bk)

Least Common Multiple (LCM)

• For two positive integers a and b, the least common multiple, denoted lcm(a, b), is the smallest positive integer divisible by both a and b
• Factoring can find the LCM by factoring a and b into their prime factorizations: a=p1^a1 * p2^a2 * p3^a3 ... pk^ak and b = p1^b1 * p2^b2 * p3^b3 ... pk^bk, then: lcm(a,b) = p1^max(a1,b1) * p2^max(a2,b2) * p3^max(a3,b3) ... pk^max(ak,bk)

Euclid's Algorithm

• Euclid's algorithm provides a more efficient method for computing the GCD, it is based on successively applying the division algorithm
• To find gcd(287, 91), divide the larger number (287) by the smaller one (91) to get 287 = 3*91 + 14
• Any divisor of 91 and 287 must also be a divisor of 14 and then gcd(287,91) = gcd(91,14)
• The same trick can be applied again

Modular Arithmetic

• Focuses on the remainder of an integer when divided by a positive integer

Congruency

• Integers a and b are congruent modulo m (a ≡ b (mod m)) if m divides a - b
• a ≡ b (mod m) if and only if a mod m = b mod m

Congruency Theorems

• Integers a and b are congruent modulo m if and only if there exists an integer k such that a = b + mk
• If a ≡ b (mod m) and c ≡ d (mod m), then:
  • 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)(b mod m)) mod m

Application of Modular Arithmetic in CS

• Modular arithmetic and congruencies are used in computer science for:
  • Pseudorandom number generators
  • Hash functions
  • Cryptology

Pseudorandom Number Generators

• Needed to simulate random choices in programs
• Linear Congruential Method: Choose 4 numbers: the modulus m, multiplier a, increment c, and seed x0, such that 2 < a <m, 0 < c < m, 0 < x0 < m
• A sequence is generated by following formula xn+1 = (a*xn + c) mod m

Hash Functions

• Algorithms that map data of arbitrary length to data of a fixed length
• Returns hash values or hash codes
• A common hash function is h(k) = k mod n, where n is the number of available storage locations

Security

Cryptology

• Caesar Cipher: Shift letters in the message by 3, mapping last three letters to the first three
  • If the index of the letter is p represented as: f(p) = (p + 3) mod 26

Cryptosystems

• A cryptosystem is a five-tuple (P, C, K, E, D), where:
  • P is the set of plaintext strings
  • C is the set of ciphertext strings
  • K is the keyspace (the set of all possible keys)
  • E is the set of encryption functions
  • D is the set of decryption functions

Public Key Cryptography

• Shift cipher is an example of private key cryptosystems
• The encryption key can easily find the decryption key, it is necessary to exchange this key safely
• Public key cryptosystems as an alternative, were Introduced in 1970s
  • Use a publicly known encryption key vs. secret decryption keys
  • An extraordinary amount of work needed to recover the plaintext message without knowing decryption keys

The RSA cryptosystem

• Developed by Ronald Rivest, Adi Shamir and Leonard Adleman (1976) from the Massachusetts Institute of Technology
• Every User as an encryption key (n, e) comprised of:
  • n: the product of two large primes p and q, say with 200 digits each.
  • e: relatively prime to (p - 1)(q – 1)

RSA encryption

• A plaintext message M is first translated into sequences of two-digit numbers
  • A is translated into 00, B into 01,..., and Jinto 09, etc.
  • Concatenate these two-digit numbers into strings of digits
  • Divide this string into equally sized blocks of 2N digits
  • 2N: the largest even number such that the number 2525 ... 25 with 2N digits does not exceed n
  • As a result, M is now translated into a sequence of integers ml,m2, ..., mk for some integer k.
  • Transform each block mi to a ciphertext block ci, following this formala: C = Me mod n

RSA decryption

• Plaintext message can be quickly recovered when the decryption key d, an inverse of e modulo (p - 1)(q – 1), is known
  • Follows the expression: Cd = (Me)d = Mde = M1+k(p-1)(q-1) (mod n)

RSA as public key system

• Because RSA cryptosystem is suitable for public key cryptography
  • Possible to rapidly construct a public key by finding two large primes p and q, each with more than 200 digits
  • Possible to find an integer e relatively prime to (p - 1)(q – 1)
  • Quickly find an inverse d of e modulo (p - 1)(q – 1)
• However, no method is known to decrypt messages that is not based on finding a factorization of n
  • The most efficient factorization methods known (as of 2010) require billions of years to factor 400-digit integers

Key exchange

• Key exchange occurs when two parties use to exchange a secret key over an insecure communications channel without having shared any information in the past

Diffie-Hellman key agreement protocol

• It happens when Suppose that Alice and Bob want to share a common key.
  • The protocol follows these steps, where the computations are done in Zp
• Alice and Bob agree to use a prime p and a primitive root a of p
• Alice chooses a secret integer k1 and sends ak1 mod p to Bob
• Bob chooses a secret integer k2 and sends ak2 mod p to Alice
• Alice computes (ak2)k1 mod p
• Bob computes (ak1)k2 mod p

Representation of Integers

• In the modem world, we use decimal, or base 10, notation to represent integers. For example when we write 965, we mean 9 * 10^2 + 6 * 10^1 + 5 * 10^0
• Numbers can be represented with any positive integer "b" as it base
  • Although base 2, 8 and 16 are important for computing and communications

Modular Exponentiation

• The expression = bak-12k-1... ba12 . bao means the same as = bak-12k-1 ... ba12 * bao
• It may be simplified by using the algorithm 5 called "modular exponentiation"