function Calculator::gcdExtended

Return value

array{string, string, string} GCD, X, Y

1 call to Calculator::gcdExtended()

Calculator::modInverse in vendor/brick/math/src/Internal/Calculator.php

Returns the modular multiplicative inverse of $x modulo $m.

File

vendor/brick/math/src/Internal/Calculator.php, line 287

Class

Calculator

Performs basic operations on arbitrary size integers.

Namespace

Brick\Math\Internal

Code

private function gcdExtended(string $a, string $b) : array {
    if ($a === '0') {
        return [
            $b,
            '0',
            '1',
        ];
    }
    [
        $gcd,
        $x1,
        $y1,
    ] = $this->gcdExtended($this->mod($b, $a), $a);
    $x = $this->sub($y1, $this->mul($this->divQ($b, $a), $x1));
    $y = $x1;
    return [
        $gcd,
        $x,
        $y,
    ];
}