Number Theory Basics I
Lecture 3
Numbers
? Integers
? Real
Arithmetic Operations
? Addition and subtraction
? Multiplication and division
? Exponentiation and logarithm
The Geometry of Numbers
? Infinity
0
Mapping Line onto Circle
? Stereographic Projection
– one-to-one mapping
x
P(x)
Mapping Line to Circle
? Wrap around
– Modular arithmetic
Modular Arithmetic
? a = b mod m iff (a-b) = km + b for some m
? Zm the equivalence class under mod m
? [a]m
? Canonical form,Zm = {0,1,2,…,m -1},we
use the positive remainder as the standard
representation
Modular Arithmetic
? -1 = m -1 mod m
? Z7 = {0,1,2,3,4,5,6}
? (Zm,+,?,0,1) defines a ring
– +,? are closed
– associative and commutative
– Operation ? distributes over +
– 0 is the identity for + and 1 for ?
– Additive inverse and multiplicative inverse
Multiplicative Inverses and
Congruence Equations
? When does a number has a multiplicative inverse?
? When does a congruence equation ax = b mod m
– has a solution
– has a unique solution
? 5x = 8 mod 12 ==> x = 4
? 3x = 8 mod 12 ==> no solution
? 3x = 9 mod 12 ==> x in {3,7,11}
Greatest Common Divisor (GCD)
? gcd(12,15) = 3
? gcd(12,25) = 1,relative prime
? Theorem,ax = b mod m has a unique
solution for every number b in Zm iff
gcd(a,m) = 1
Proof
? Consider the map,Pa (x) = ax,
Suppose x ? y and ax = ay mod m
then a(x-y) = 0 mod m,So if gcd(a,m) =1,
then x = y mod m,Therefore,it is a
bijection,Therefore,every ax = b mod m
has a unique solution
? In particular ax = 1 mod m has a solution,
which implies that a has an inverse
Multiplication Group
? Z*m = {a,gcd(a,m) = 1}
? Euler phi function f(m) = | Z*m |
? If m is a prime then
? f(m) = m -1,and
? f(md) = md - md-1
Euclid’s Algorithm
(First non-trivial algorithm known)
GCD(r0,r1) = GCD(r1,r0 -r1)
= GCD(r1,r0 mod r1)
Each iteration,the total number of bits in the two numbers
is reduced by at least 1 ==> number of recursion is
O(|input|)
Division,naively,takes O(|input|2) operations,
FFT method for Division,O(|input| log (|input|))
A sample run
? GCD(75,28)
? 75 = 2 ? 28 + 19
? 28 = 1 ? 19 + 9
? 19 = 2 ? 9 + 1
? 9 = 9 ? 1
? GCD(75,28) = 1,relative prime
Breakdowns
? GCD(r0,r1)
? GCD(r0,r1) = GCD(rm-1,rm) = rm
? r0 = q1 r1 + r2
? r1 = q2 r2 + r3
? …
? rm-2 = qm-1 rm-1 + rm
? rm-1 = qm rm
? GCD(r0,r1) = GCD(rm-1,rm) = rm
Computing Multiplicative Inverse
? r1-1 mod r0 exists iff GCD(r0,r1) = 1
? ==> rm= 1
? Would like to fine t such that r1 t = 1 mod r0
? Recursively find r1 tk = rk mod r0
? t0 = 0,t1 = 1,and
? tk = tk-2 -qk-1 tk-1 mod r0
A sample run
? GCD(75,28)
? 75 = 2 ? 28 + 19
? 28 = 1 ? 19 + 9
? 19 = 2 ? 9 + 1
? 9 = 9 ? 1
? GCD(75,28) = 1
? t0 = 0,
? t1 = 1,
? t2 = 0-2?t1 = 73 mod 75
? t3 = 1-1?t2 = 3 mod 75
? t4 = 73-2?t3 = 67 mod 75
tk = tk-2 -qk-1 tk-1 mod r0
Building Public Key System
? One-way function,f() is one way if
– For any x,y = f(x) is easy to compute
– For any (or almost all) y,it is hard to find an x
such that f(x) = y
? Trapdoor one-way function fs()
– given s and y,it is easy to compute an x such
that fs(x) = y
Knapsack Scheme
(Merkel and Hellman,1978)
? Given X = (x1,x2,…,x n ) and a integer s
? Finding B = (b1,b2,…,b n ) where bi = 0 or 1
such that
s = bi xi= < X,B> = ? bi xi
? NP-Complete in general
Complexity Theory
? Decision Problem
– Decide whether there exists a solution
? Search Problem
– Find a solution if there is one
Complexity Theory
EXPTIME
PSPACE
Polynomial-Hierarchy
NP
P Linear
Super-Increasing Sequence
? X = (x1,x2,…,x n ) is superincreasing if
?
?
?
?
1
1
i
j
ji xx
? (2,3,6,13,27,52 ) is superincreasing
Greedy Method
? Solve X = (2,3,6,13,27,52 ) and s = 70
? s > 52? Yes ==> b6 = 1,s1 = 70 - 52 = 18
? 18 > 27? No ==> b5 = 0
? 18 > 13? Yes ==> b4 = 1,s2 = 18 - 13 = 5
? 5 > 6? No ==> b3 = 0
? 5> 3? Yes ==> b2 = 1,s2 = 5 - 3 = 2
? b1= 1
? B = (1,1,0,1,0,1)