고속 누승 알고리즘

powMod.js

/**
 * 고속 누승 알고리즘 구현.
 * x^p mod(m) 계산
 * 참고: http://a.nex.kr.pe/wordpress/2015/10/21/제-6강-고속-누승-알고리즘과-모듈러/
 * @method powMod
 * @param  {int}    x   피제수
 * @param  {int}    p   지수
 * @param  {int}    m   제수
 * @return {int}        x^p mod(m) 계산 결과값
 */
function powMod(a, b, n){
    let result = 1;

    while(b)
   {
      if(b & 1)
      {
         result = (result * a) % n ;
      }
       b = parseInt(b / 2);
       a  = (a * a) % n ;
   }
   return result;
}