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))