function NativeCalculator::modPow

Algorithm from: https://www.geeksforgeeks.org/modular-exponentiation-power-in-modular-a…

Overrides Calculator::modPow

File

vendor/brick/math/src/Internal/Calculator/NativeCalculator.php, line 210

Class

NativeCalculator

Calculator implementation using only native PHP code.

Namespace

Brick\Math\Internal\Calculator

Code

public function modPow(string $base, string $exp, string $mod) : string {
    // special case: the algorithm below fails with 0 power 0 mod 1 (returns 1 instead of 0)
    if ($base === '0' && $exp === '0' && $mod === '1') {
        return '0';
    }
    // special case: the algorithm below fails with power 0 mod 1 (returns 1 instead of 0)
    if ($exp === '0' && $mod === '1') {
        return '0';
    }
    $x = $base;
    $res = '1';
    // numbers are positive, so we can use remainder instead of modulo
    $x = $this->divR($x, $mod);
    while ($exp !== '0') {
        if (in_array($exp[-1], [
            '1',
            '3',
            '5',
            '7',
            '9',
        ])) {
            // odd
            $res = $this->divR($this->mul($res, $x), $mod);
        }
        $exp = $this->divQ($exp, '2');
        $x = $this->divR($this->mul($x, $x), $mod);
    }
    return $res;
}