Discrete Mathematics - Number Theory II

Discrete Mathematics

Number Theory II

Edgar SIMO-SERRA

Today’s Class

Turing Codes
RSA

Greatest Common Divisor (Review)

Definition. $gcd(a,b) ::=$ the greatest common divisor of $a$ and $b$

Definition. $a$ and $b$ are relatively prime if $gcd(a,b)=1$

Encryption

Definition. $x$ is a congruent to $y$ modulo $n$ : $x\equiv y (\text{mod}\; n) \iff n \mid (x-y)$

Definition. The multiplicative inverse of $x \;\text{mod}\; n$ is a number $x^{-1} \in \{0,1,\ldots,n-1\}$ s.t. $x x^{-1} \equiv 1 (\text{mod}\; n)$

congruent example: $2\cdot 3 \equiv 1 (\text{mod }n)$ because $n \mid (31-16)$

multiplicative inverse example: $2\cdot 3 \equiv 1 (\text{mod } 5)$ , $2 \equiv 3^{-1} (\text{mod } 5)$ , $3 \equiv 2^{-1} (\text{mod } 5)$

$5\cdot 5 \equiv 1 (\text{mod } 6)$ , $5 \equiv 5^{-1} (\text{mod } 6)$

Useful Theorems

Definition. (Euler’s Totient Function) $\phi(n)$ denotes the number of integers in ${1,2,3,\ldots,n-1}$ that are relatively prime to $n$

Euler’s Theorem. $gcd(n,k)=1 \implies k^{\phi(n)} \equiv 1 (\text{mod}\;n)$

Fermat’s (Little) Theorem. Suppose $p$ is prime and $k \in \{1,2,\ldots,p-1\}$ , then $k^{p-1} \equiv 1 (\text{mod}\; p)$

RSA (Rivest–Shamir–Adleman)

Public key encryption
Widely used all over (ssh, etc.)
Based on the assumption that it is hard to factor two large primes

Next Class

Graph Theory Fundamentals
Graph Coloring Problem

Discrete Mathematics Number Theory II Edgar SIMO-SERRA