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;
}

18 июня 2003 14:19

Сергей (инкогнито)
18 июня 2003, 20:19

Оффтопик.

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

bolk (bolknote.ru)
18 июня 2003, 20:19, ответ предназначен Сергей

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

Ivan (инкогнито)
18 июня 2003, 20:36

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;
}

bolk (bolknote.ru)
18 июня 2003, 20:36, ответ предназначен Ivan

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

Ваше имя или адрес блога (можно OpenID):

Текст вашего комментария, не HTML:

Кому бы вы хотели ответить (или кликните на его аватару)