Transcript Number-Theoretic Algorithms

Number-Theoretic Algorithms
• Modern cryptography is based on number theory
and, in particular, the inability to factor the
product of large prime numbers
• The major topics include
–
–
–
–
–
–
–
modular arithmetic
Euclid’s algorithm to solve a x  b (mod n)
the Chinese remainder theorem
efficient computing of ab mod n
the RSA public key cryptosystem
finding large prime numbers efficiently
factoring integers
Operations on large integers
• Basic concepts
– We measure the size in the number of bits
– for integer a1a2…ak a polynomial time algorithm is
polynomial in lg a1, lg a2, … , lg ak
– we count the number of bit operations, such as
multiplication of two b-bit integers takes O(b2) time
• Set notation
– Z is the set of integers { …, -2, -1, 0, 1, 2, …}
– N is the set of natural numbers {0, 1, 2, 3, … }
Basic notation and concepts
• Notation
– d | a means that “d divides a” or “a is a multiple of d”
– 1 and a are “trivial” divisors; a number is prime if its
only divisors are the trivial divisors; a non-prime
number is composite
– q = a/n is the quotient
– r = a mod n is the remainder
Modular Notation
• Notation
– a  b (mod n) means (a mod n) = (b mod n)
– a  b (mod n) iff n | (b - a)
• Equivalence class modulo n
– [a]n = {a + k n : k  Z}
– Z n = { [a] n : 0 <= a <= n-1 }
• Common divisors
– d | a and d | b implies d | (ax + by) for integers x,y
– a | b and b | a implies a =  b
– gcd(a,b) where a and b are not both zero is the largest
of the common divisors of a and b
Greatest Common Divisors
Relatively Prime & Unique Factorization
• Two integers are relatively prime if their only
common divisor is one
• Unique Factorization