note 80479 added to function.bcdiv
| From: | MM at osu1 dot php dot net | Date: | Fri, 18 Jan 2008 11:29:14 +0000 |
| Subject: | note 80479 added to function.bcdiv | ||
| Groups: | php.notes | ||
| Request: | Send a blank email to php-notes+get-135186@lists.php.net to get a copy of this message | ||
Perhaps some one can find useful this function to compute the modular inverse of a integer (extended
euclidean algorithm):
function invmod($a,$b) {
$n=$b;
$x=0; $lx=1; $y=1; $ly=0;
while ($b) {
$t=$b;
$q=bcdiv($a,$b,0);
$b=bcmod($a,$b);
$a=$t;
$t=$x; $x=bcsub($lx,bcmod(bcmul($q,$x),$n)); $lx=$t;
$t=$y; $y=bcsub($ly,bcmod(bcmul($q,$y),$n)); $ly=$t;
}
if (bccomp($lx,0) == -1)
$lx=bcadd($lx,$n);
return $lx;
}
// verify
$n="2447995268898324993537772139997802321";
$t="64941057316178801556773346239351236811";
$m="123456789";
$i=invmod($t,$n);
// (t*m)*inv(t) is m
echo bcmod(bcmul(bcmod(bcmul($t,$m),$n),$i),$n) == $m;
----
Server IP: 130.206.1.5
Probable Submitter: 89.128.67.11
----
Manual Page -- http://www.php.net/manual/en/function.bcdiv.php
Edit -- https://master.php.net/note/edit/80479
Del: integrated -- https://master.php.net/note/delete/80479/integrated
Del: useless -- https://master.php.net/note/delete/80479/useless
Del: bad code -- https://master.php.net/note/delete/80479/bad+code
Del: spam -- https://master.php.net/note/delete/80479/spam
Del: non-english -- https://master.php.net/note/delete/80479/non-english
Del: in docs -- https://master.php.net/note/delete/80479/in+docs
Del: other reasons-- https://master.php.net/note/delete/80479
Reject -- https://master.php.net/note/reject/80479
Search -- https://master.php.net/manage/user-notes.php