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