Форумы портала PHP.SU :: Версия для печати :: Возведение в степень по модулю

1. iflight - 30 Апреля, 2011 - 11:02:58 - перейти к сообщению

По учебе надо реализовать RSA(http://ru.wikipedia.org/wiki/RSA) в примитивном виде, т.е. ключи можно брать достаточно маленькие.
Сами ключи вроде как сгенерировал, хоть и понимаю что далеко не лучшим способом.

PHP:
скопировать код в буфер обмена

function is_easy($numb) {                       //функция проверки на чистоту
 if(($numb % $i) == 0) { return false; break;}
 }
 return true;
}
 
function get_nod($a,$b) { //нахождение НОД по алгоритму Евклида
$ar=$a;
$br=$b;
        do{
                if($ar<$br){
                $br=$br%$ar;
                }else{
                $ar=$ar%$br;
                }
        } while($ar!==0 && $br!==0);
return max($ar,$br);    
}
 
 
 
do {            // Генерим простое число p
$p=mt_rand(100,500);
} while(is_easy($p)<> true);
 
do {                // Генерим простое число q
$q=mt_rand(100,500);
} while(is_easy($q)<> true);
 
$n = $p*$q;  //считаем n
 
$eyler = ($p-1)*($q-1); // считаем функцию Эйлера
 
do {                // Генерим e
        $e=mt_rand(3,50);
} while(get_nod($e,$eyler)!==1);
 
do {                // Генерим d
        $d=mt_rand();
} while((($e*$d)%$eyler)!==1);

Ключи выходят например такие: q=439 n=184819 Эйлейр=183960 e=23 d=2121052239

Проблемма возникла на самом кодировании, т.е. возведении в степень по модулю. Использовал такую функцию:

PHP:
скопировать код в буфер обмена

function powmod($a, $b, $c)
{
    $z = 1;
 
    while ($b) 
    {
        if ($b % 2 == 0) 
        {
             $b = $b/2;
             $a = ($a * $a) % $c;
        }
        else 
        {
             $b--;
             $z = ($z * $a) % $c;
         }
     }
     return $z;
}

С мелкими числами считает нормально (например ключи (3,33) и (7,33)), но с сгенерированными мною нет, подставлял пример из вики, так же считает не правильно.

В таком программировании не шарю) Весь опыт работы с php сводится к web) Подскажите, может где ошибка, направьте на путь истинный)