Как рассчитать 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 

Алгоритм известен как экспоненциации путем возведения в квадрат или квадрат и умножаем метод.