x^y mod z를 계산하는 방법?

Question

x^y mod z를 계산하는 방법이 궁금합니다. x와 y는 매우 커서 (64 비트 정수에 맞지 않음) z는 64 비트 정수에 맞습니다. 그리고 x^y mod z와 같은 답을주지 않는 것은 (x mod z)^y mod z와 같습니다.

Answer 1

Java를 사용하는 경우 x, y 및 z를 BigInteger로 변환하십시오.

BigInteger xBI = new BigInteger(x); 
BigInteger yBI = new BigInteger(y); 
BigInteger zBI = new BigInteger(z); 
BigInteger answer = xBI.modPow(yBI,zBI); 

Answer 2

다음 의사 코드에서, 표준 방법이다

function powerMod(b, e, m) 
    x := 1 
    while e > 0 
     if e % 2 == 1 
      x := (b * x) % m 
      e := e - 1 
     else 
      b := (b * b) % m 
      e := e/2 
    return x 

알고리즘은 또는 평방 및 방법 곱하기 제곱 지수로 알려져있다.