1 заметка с тегом

алгоритмы

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

2003   php   алгоритмы   программирование