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.mod n, where b-l is the inverse of 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)+(b c)mod n Additive and multiplicative identity a+0=a mod n and a*l= 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 o a*a1=1modn, for all a≠0 Can chose whether to do an operation and then reduce modulo n, or reduce then do the operation Since reauction is a homomorphism Irom 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 b=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 ·ife:=0then 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(og, 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 bl=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
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 g.c.d(a, b) without needing to factor a and 6e The euclidian algorithm is a way of finding the ng assume a>b First find q and r such as a=b*q+r Then find q2 and r 2 such as b=g2* r+r2 Find qs and rs using r- 2=q r +r for i2 until; =0 g.c.d. (a,b= 1-1 The Euclidian algorithm runs in O(log(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-g.cd(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(oga) 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 Algorithm The algorithm Inverse(a, n) is given by -9=nu=1vo=0 -91=au1=0v1=1 - let y=gi-1 div gi 9+1=91-y*g=g1modg1 u#+1=u1-y Vi-1-y when g=0 then inverse(a, n )=VM-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