Функции криптосистемы Рабина

Question

Я пытаюсь реализовать криптосистему Рабина , и я застрял на этапе расшифровки.Мне нужно решить:

Y _p * p + Y _p * q = 1

и вычислить Yp и Yq, когда p и q известны (даны).

Давайте возьмем пример из Википедии, поэтому p = 7 и q = 11;Тогда у нас будет:Yp * 7 + Yq * 11 = 1;

Используя расширенный евклидов алгоритм , мы должны получить результат:Yp = -3 и Yq = 2;

Вот псевдокод из Wiki:

//pseudo code
function extended_gcd(a, b)
if b = 0
    return (1, 0)
else
    (q, r) := divide (a, b)
    (s, t) := extended_gcd(b, r)
    return (t, s - q * t)

---

Вот что я сделал до сих пор:

//q = 11; p = 7;
$arr = array(11, 7); //test  number from wiki; 
$result = extendedGcd($arr); //output array(0,1)
                             //but should be: array(-3, 2); (from wiki example)
...
//Legend: arr[0] = a; arr[1] = b;   
function extendedGcd($arr){
    if ($arr[1] == 0) return array(1, 0);
    else{
        //( (q, r) := divide (a, b) ) == ( q := a div b, r = a − b * q );
        $q = floor($arr[0] / $arr[1]); $r = $arr[0] - $arr[1] * $q;
        $tmp = extendedGcd($arr[1], $r); 
        $s = $tmp[0]; $t = $tmp[1];
        return array($t, $s - $q * $t);
    }
}

Я не знаю что не так.Как я могу рассчитать Yp и Yq?

Решаемые.Если кто-то ищет это в PHP:Рекурсивный метод:

//thank to NullUserException ఠ_ఠ
function extendedGcd($arr){
 if ($arr[1] == 0) return array(1, 0);
 else{
    $q = floor($arr[0] / $arr[1]);
    $r = $arr[0] % $arr[1];
    $temp = extendedGcd(array($arr[1], $r));
    $s = $temp[0]; $t = $temp[1];
    return array($t, $s - $q * $t);
 }
}

Нерекурсивный.(Я знаю, это выглядит некрасиво, все еще это работает.

function extendedGcd($a, $b){
 $x = 0;    $lastx = 1;
 $y = 1;    $lasty = 0;
 while ($b != 0){ //while b ≠ 0
    $quotient = floor($a / $b);
    $tempA = $a; $a = $b; $b = $tempA % $b;
    echo '<br />$a = '.$a.'; $b = '.$b;
    echo '<br />$quotient = '.$quotient;
    $tempX = $x;
    $x = $lastx - $quotient * $x;
    $lastx = $tempX;
    $tempY = $y;
    $y = $lasty - $quotient * $y;
    $lasty = $tempY;       
    echo '<br />$lastx = '.$lastx.'; $lasty = '.$lasty.'<hr />'; 
 }
 return array($lastx, $lasty);
}

Answer 1

Ваша проблема заключалась в том, что вы вызывали extendedGcd() примерно так: extendedGcd($arr[1], $r);, когда на самом деле он принимал только один аргумент (массив).Вот как я бы переписал функцию:

function extendedGcd($a, $b){
    if ($b == 0) 
        return array(1, 0);

    $q = floor($a / $b); 
    $r = $a % $b;        // PHP does have a modulus operator

    list($s, $t) = extendedGcd($b, $r); 
    return array($t, $s - $q * $t);
}

print_r(extendedGcd(11, 7));

, которая дает ожидаемый результат .

---

PS: в процессе проверки правильностиалгоритм, я использовал эту функцию Python:

def extended_gcd(a, b):
    if b == 0:
       return (1, 0)

    else:
        (q, r) = (a/b, a%b)
        (s, t) = extended_gcd(b, r)
        return (t, s - q * t)

Неимоверно красиво, не правда ли?