Number Theory
? Modular arithmetic
– Used to define a finite field
– a = b mod n means that if a and b are divided
by n they produce the same remainder
– a*b mod n can result in 0 even if a and b are
not 0
– a/b mod n is calculated by a*b-1 mod n,where
b-1 is the inverse of b,b*b-1 = 1 mod n
Number Theory
? Integers modulo n with addition and multiplication
form a commutative ring with the laws of
– Associativity
? (a+b)+c = a+(b+c) mod n (also for multiplication)
– Commutativity
? a+b = b+a mod n (also for multiplication)
– Distributivity
? (a+b).c = (a.c)+(b.c) mod n
– Additive and Multiplicative identity
? a+0 = a mod n and a*1= a mod n
– Additive inverse
? a+(-a) = 0 mod n
Number Theory
? A Field is a set that has the same properties as the
commutative ring plus a multiplicative inverse for
all elements but 0
– a*a-1 = 1 mod n,for all a ? 0
? Can chose whether to do an operation and then
reduce modulo n,or reduce then do the operation,
since reduction is a homomorphism from the ring
of integers to the ring of integers modulo n
– a op b mod n = [a mod n op b mod n] mod n
– Where op can be +,-,or *
Number Theory
? If n is constrained to be a prime number p then
this forms a Galois Field modulo p denoted GF(p)
and all the normal laws associated with integer
arithmetic work
? Exponentiation in GF(p)
– many encryption algorithms use exponentiation -
raising a number a (base) to some power b (exponent)
mod p
– b = ae mod p
– exponentiation is basically repeated multiplication,
which take s O(n) multiplies for a number n
Number Theory
? Exponentiation in GF(p)
– a better method is the square and multiply algorithm
– let base = a,result =1
– for each bit ei (LSB to MSB) of exponent
? if ei=0 then
– square base mod p
? if ei=1 then
– multiply result by base mod p
– square base mod p (except for MSB)
– required ae is result
– only takes O(log2 n) multiplies for a number n
Number Theory
? Discrete Logarithms in GF(p)
– the inverse problem to exponentiation is that of finding
the discrete logarithm of a number modulo p
– find x where ax = b mod p
– while exponentiation is relatively easy,finding discrete
logarithms is generally a hard problem,with no easy
way
– in this problem,we can show that if p is prime,then
there always exists an a such that there is always a
discrete logarithm for any b!=0
? successive powers of a "generate" the group mod p
– such an a is called a primitive root and these are also
relatively hard to find
Euclidian Algorithm
? The Euclidian Algorithm is a way of finding the
g.c.d.(a,b) without needing to factor a and b,
– Assume a>b
– First find q1 and r1 such as a=b*q1+r1
– Then find q2 and r2 such as b = q2*r1+r2
– Find q’s and r’s using ri-2=qi*ri-1+ri for i>2 until ri=0,
– g.c.d.(a,b)=ri-1
? The Euclidian algorithm runs in O(log3(a))
Euclidian Algorithm
? Example,
– Find g.c.d.(1547,560)
– 1547 = 2*560+427
– 560= 1*427 + 133
– 427 = 3*133 + 28
– 133 = 4*28 + 21
– 21 = 1*21 + 7
– 21 = 3*7 + 0
– Thus g.c.d(1547,560) = 7
Extended Euclidian GCD
Algorithm
? In some cryptographic algorithm you want to find
a inverse a-1 such as a*a-1=1 mod n
? We use the fact that
– if d = g.c.d.(a,b),where a>b,then there exists integer u
and v such that d = u*a + v*b,
– finding u and v can be done in O(log3a)
? Then we use an extended Euclidian algorithm to
find a-1,assuming g.c.d.(a,n) = 1
Extended Euclidian GCD
Algorithm
? The algorithm
– Inverse(a,n) is given by,
– g0=n u0=1 v0=0
– g1=a u1=0 v1=1
– let
? y = gi-1 div gi
? gi+1 = gi-1 – y*gi = gi-1 mod gi
? ui+1 = ui-1 – y*ui
? vi+1 = vi-1 – y*vi
– when gi=0 then inverse(a,n) = vi-1
Extended Euclidian GCD
Algorithm
? Example,
– Find inverse of 3 mod 460
i y g u v
0 - 460 1 0
1 - 3 0 1
2 153 1 1 -153
3 3 0 -3 460
– So,3-1 mod 460 = -153 mod 460 = 307 mod 460
Euler phi-function
? Euler ? function
– ?(n) = | (0?b<n) | g.c.d.(b,n) = 1) |
– If p is prime than ?(p) = p-1
– ?(m*n) = ?(m)* ?(n),if g.c.d.(m,n) = 1
– ?(p?)=p? - p?-1
Fermat’s Little Theorem
? Let p be a prime
? Any integer that satisfies ap = a mod p and
any integer a not divisible by p satisfies
– ap-1=1 mod p
? Generalization of Fermat’s Little Theorem
due to Euler,
– If g.c.d.(a,m) = 1,then a?(m)=1 mod m
Algorithms to find Inverses
? Algorithms to find Inverses a-1 mod n
1.Search 1,...,n-1 until an a-1 is found with a.a-1
mod n
2.if ?(n) is known,then from Euler's
Generalization
? a-1 = a ? (n)-1 mod n
3.Otherwise use Extended Euclid's algorithm for
inverse
Chinese Remainder Theorem
? Motivation,
– Find a number x that leaves a remainder of 1
when divided by 3,2 when divided by 5 and 3
when divided by 7,So,x=1 mod 3,x = 2 mod 5
and x = 3 mod 7
? We want to solve a system of congruences
to different moduli
Chinese Remainder Theorem
? The system is
– x = a1 mod m1
– x = a2 mod m2
– …,
– x = ar mod mr
– Assume that g.c.d.(mi,mj) = 1 for i ?j,The
system has a unique solution modulo
M=m1m2…m r
Chinese Remainder Theorem
? The Chinese remainder theorem provides a
way of solving an equation mod n,where
n=p*q and p and q are prime,solving
equations mod p and mod q
– Consider b1 = q-1 mod p and b2 = p-1 mod q
– If a = a1b1q+a2b2p we have that
? a = a1b1q+a2b2p = a1 mod p
? a = a1b1q+a2b2p = a2 mod q
– So if I know a1 and b1 I know a
Chinese Remainder Theorem
? Example
– Solve x = 5 mod 7 and x = 6 mod 11
– 7-1 mod 11 = 8
– 11-1 mod 7 = 2
– So a = 5 * 2 * 11 + 6 * 8 * 7 = 446
– a = 61 mod 77 is the solution for both equations
Quadratic Residues
? ap-1-1=(a(p-1)/2-1) (a(p-1)/2+1) = 0 mod p
? We define the Legendre symbol by,
?+1 if a(p-1)/2 = +1 mod p and a ? 0 mod p
= ?-1 if a(p-1)/2 = -1 mod p and a ? 0 mod p
?0 if a = 0 mod p
? This implies that a(p-1)/2 = mod p
? More generally,given the prime
factorization we define the Jacobi
Symbol
???
?
???
?
p
a
????????pa
ppp rrrn kk...21 21?
r
a
r
a
r
a
n
a k
ppp k ?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
??
?
??
?
?,..
21
21
Quadratic Residues
? a is a quadratic residue module p if and only
if ?b ?Z*p ( a = b2 mod p)
? a is a quadratic residue if and only if
= 1
???
?
???
?
p
a
? Modular arithmetic
– Used to define a finite field
– a = b mod n means that if a and b are divided
by n they produce the same remainder
– a*b mod n can result in 0 even if a and b are
not 0
– a/b mod n is calculated by a*b-1 mod n,where
b-1 is the inverse of b,b*b-1 = 1 mod n
Number Theory
? Integers modulo n with addition and multiplication
form a commutative ring with the laws of
– Associativity
? (a+b)+c = a+(b+c) mod n (also for multiplication)
– Commutativity
? a+b = b+a mod n (also for multiplication)
– Distributivity
? (a+b).c = (a.c)+(b.c) mod n
– Additive and Multiplicative identity
? a+0 = a mod n and a*1= a mod n
– Additive inverse
? a+(-a) = 0 mod n
Number Theory
? A Field is a set that has the same properties as the
commutative ring plus a multiplicative inverse for
all elements but 0
– a*a-1 = 1 mod n,for all a ? 0
? Can chose whether to do an operation and then
reduce modulo n,or reduce then do the operation,
since reduction is a homomorphism from the ring
of integers to the ring of integers modulo n
– a op b mod n = [a mod n op b mod n] mod n
– Where op can be +,-,or *
Number Theory
? If n is constrained to be a prime number p then
this forms a Galois Field modulo p denoted GF(p)
and all the normal laws associated with integer
arithmetic work
? Exponentiation in GF(p)
– many encryption algorithms use exponentiation -
raising a number a (base) to some power b (exponent)
mod p
– b = ae mod p
– exponentiation is basically repeated multiplication,
which take s O(n) multiplies for a number n
Number Theory
? Exponentiation in GF(p)
– a better method is the square and multiply algorithm
– let base = a,result =1
– for each bit ei (LSB to MSB) of exponent
? if ei=0 then
– square base mod p
? if ei=1 then
– multiply result by base mod p
– square base mod p (except for MSB)
– required ae is result
– only takes O(log2 n) multiplies for a number n
Number Theory
? Discrete Logarithms in GF(p)
– the inverse problem to exponentiation is that of finding
the discrete logarithm of a number modulo p
– find x where ax = b mod p
– while exponentiation is relatively easy,finding discrete
logarithms is generally a hard problem,with no easy
way
– in this problem,we can show that if p is prime,then
there always exists an a such that there is always a
discrete logarithm for any b!=0
? successive powers of a "generate" the group mod p
– such an a is called a primitive root and these are also
relatively hard to find
Euclidian Algorithm
? The Euclidian Algorithm is a way of finding the
g.c.d.(a,b) without needing to factor a and b,
– Assume a>b
– First find q1 and r1 such as a=b*q1+r1
– Then find q2 and r2 such as b = q2*r1+r2
– Find q’s and r’s using ri-2=qi*ri-1+ri for i>2 until ri=0,
– g.c.d.(a,b)=ri-1
? The Euclidian algorithm runs in O(log3(a))
Euclidian Algorithm
? Example,
– Find g.c.d.(1547,560)
– 1547 = 2*560+427
– 560= 1*427 + 133
– 427 = 3*133 + 28
– 133 = 4*28 + 21
– 21 = 1*21 + 7
– 21 = 3*7 + 0
– Thus g.c.d(1547,560) = 7
Extended Euclidian GCD
Algorithm
? In some cryptographic algorithm you want to find
a inverse a-1 such as a*a-1=1 mod n
? We use the fact that
– if d = g.c.d.(a,b),where a>b,then there exists integer u
and v such that d = u*a + v*b,
– finding u and v can be done in O(log3a)
? Then we use an extended Euclidian algorithm to
find a-1,assuming g.c.d.(a,n) = 1
Extended Euclidian GCD
Algorithm
? The algorithm
– Inverse(a,n) is given by,
– g0=n u0=1 v0=0
– g1=a u1=0 v1=1
– let
? y = gi-1 div gi
? gi+1 = gi-1 – y*gi = gi-1 mod gi
? ui+1 = ui-1 – y*ui
? vi+1 = vi-1 – y*vi
– when gi=0 then inverse(a,n) = vi-1
Extended Euclidian GCD
Algorithm
? Example,
– Find inverse of 3 mod 460
i y g u v
0 - 460 1 0
1 - 3 0 1
2 153 1 1 -153
3 3 0 -3 460
– So,3-1 mod 460 = -153 mod 460 = 307 mod 460
Euler phi-function
? Euler ? function
– ?(n) = | (0?b<n) | g.c.d.(b,n) = 1) |
– If p is prime than ?(p) = p-1
– ?(m*n) = ?(m)* ?(n),if g.c.d.(m,n) = 1
– ?(p?)=p? - p?-1
Fermat’s Little Theorem
? Let p be a prime
? Any integer that satisfies ap = a mod p and
any integer a not divisible by p satisfies
– ap-1=1 mod p
? Generalization of Fermat’s Little Theorem
due to Euler,
– If g.c.d.(a,m) = 1,then a?(m)=1 mod m
Algorithms to find Inverses
? Algorithms to find Inverses a-1 mod n
1.Search 1,...,n-1 until an a-1 is found with a.a-1
mod n
2.if ?(n) is known,then from Euler's
Generalization
? a-1 = a ? (n)-1 mod n
3.Otherwise use Extended Euclid's algorithm for
inverse
Chinese Remainder Theorem
? Motivation,
– Find a number x that leaves a remainder of 1
when divided by 3,2 when divided by 5 and 3
when divided by 7,So,x=1 mod 3,x = 2 mod 5
and x = 3 mod 7
? We want to solve a system of congruences
to different moduli
Chinese Remainder Theorem
? The system is
– x = a1 mod m1
– x = a2 mod m2
– …,
– x = ar mod mr
– Assume that g.c.d.(mi,mj) = 1 for i ?j,The
system has a unique solution modulo
M=m1m2…m r
Chinese Remainder Theorem
? The Chinese remainder theorem provides a
way of solving an equation mod n,where
n=p*q and p and q are prime,solving
equations mod p and mod q
– Consider b1 = q-1 mod p and b2 = p-1 mod q
– If a = a1b1q+a2b2p we have that
? a = a1b1q+a2b2p = a1 mod p
? a = a1b1q+a2b2p = a2 mod q
– So if I know a1 and b1 I know a
Chinese Remainder Theorem
? Example
– Solve x = 5 mod 7 and x = 6 mod 11
– 7-1 mod 11 = 8
– 11-1 mod 7 = 2
– So a = 5 * 2 * 11 + 6 * 8 * 7 = 446
– a = 61 mod 77 is the solution for both equations
Quadratic Residues
? ap-1-1=(a(p-1)/2-1) (a(p-1)/2+1) = 0 mod p
? We define the Legendre symbol by,
?+1 if a(p-1)/2 = +1 mod p and a ? 0 mod p
= ?-1 if a(p-1)/2 = -1 mod p and a ? 0 mod p
?0 if a = 0 mod p
? This implies that a(p-1)/2 = mod p
? More generally,given the prime
factorization we define the Jacobi
Symbol
???
?
???
?
p
a
????????pa
ppp rrrn kk...21 21?
r
a
r
a
r
a
n
a k
ppp k ?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
??
?
??
?
?,..
21
21
Quadratic Residues
? a is a quadratic residue module p if and only
if ?b ?Z*p ( a = b2 mod p)
? a is a quadratic residue if and only if
= 1
???
?
???
?
p
a
