Это сайт — моя персональная записная книжка. Интересна мне, по большей части, история, своя жизнь и немного программирование.

PHP modpow

Писал алгоритм ассеметричного шифрования на PHP, оказалось, что при возведении числа в большую степень очень часто возникает переполнение, а после подсчёта положительного модуля от положительного числа, часто результат оказывается отрицательным. Поскольку библиотека для работы с большими числами в PHP4 стандартно не компилируется, пришлось писать свои функции. Со степенью поясню — мне нужно было вычислять A ^ B mod C, так что фукнция именно это и делает. Кстати, не спрашивайте почему я поставил floor($a) в первой функции — так надо, иначе результат получается дробным, даже если оба числа — целые.

function m_mod($a, $b)
{
return floor($a) — floor($a/$b)*$b;
};

function m_powmod($d, $p, $m)
{
for ($b = 1; $p;)
if ($p & 1)
{
$p--;
$b = m_mod($b * $d, $m);
} else
{
$p >>= 1;
$d = m_mod($d * $d, $m);
};

return $b;
}

4 комментария
Сергей 2003

Оффтопик.

а почему не все сообщения транслируются в жж? Извини, если вопрос глупый.

Евгений Степанищев (bolknote.ru) 2003

Комментарий для Сергей:

потому что не все сообщения я туда транслирую :)

Ivan 2003

function m_powmod($d, $p, $m)
{
  for ($b = 1; $p;)
  if ($p & 1) {
    $p-​-​;
    $b = $b*$d%$m;
  } else {
    $p >>= 1;
    $d = pow($d%$m,2)%$m;
  }
  return $b;
}

Евгений Степанищев (bolknote.ru) 2003

Комментарий для Ivan:

У меня % не справлялся с большими числами.