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