bcdiv

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;