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 o even if a and b are not o a/b mod n is calculated by a b-l mod n, where b-l is the inverse ofb. b*b-l=l mod n
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 atb= bta mod n(also for multiplication) Distributivity (a+b)c=(ac)+(bc)mod n Additive and mul ultiplicative identity a +0= a mod n and a *1=a mod n Additive inverse a+(-a)=0 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 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 • 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 a mod p exponentiation is basically repeated multiplication, which take s O(n)multiplies for a number n
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 e ( LSB to MSB)of exponent if e =0 then square base mod p if e =1 then multiply result by base mod p square base mod p(except for MsB) required a is result only takes O(log 2 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 al ways exists an a such that there is al ways a discrete logarithm for any b!=0 successive powers ofa"generate"the group mod p such an a is called a primitive root and these are also relatively hard to find
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 q and r, such as a=b*+, Then find q2 and r2 such as b=g2*r+r Find qs and rs using r- 2=qr+r for i>2 until r=0 g.c.d. (a,b)=r-I The Euclidian algorithm runs in O(og(a)
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
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-I such as a*a-l=1 mod n We use the fact that if d=gcd (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 odog a Then we use an extended euclidian algorithm to find a", assuming g.c.d. (a, n)=1
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 Algorith The algorithm Inverse( a, n)is given by 9o=nu=1v=0 g1=au1=0v1= -let y=gm-1 div gi g+1=g1-y gi= gm-1 mod g 1=u-1-y"u1 1= Vi-1-yVi when gi=0 then inverse(a, )=Vi-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