pow mod

상당히 빠른 pow 계산 알고리즘. 승수를 2진수로 바꾸어 계산.

   n     b1b2b3b4     b1b2b3 0   b4      b1b2b3   b4
 x   = x          = x          x    = xx        x    = ...
 
                           10                   1
   5    101    100   1    2    1     10   1    2   1
 3   = 3    = 3    3   = 3    3   = 9   3   = 9   3  = 81 x 3
 

code

def pow(x, y):
  r = 1
  while y != 0:
    if y & 1:
      r *= x
    y = y >> 1
    x = x**2
  return r

그래서 powmod 는 다음과 같이

def powmod(x, y, n):
  r = 1
  while y != 0:
    if y & 1:
      r *= x
      r %= n
    y = y >> 1
    x = x**2
    x %= n
  return r