"Theorème des restes Chinois"... pour les amoureux de l'algorithmic Algebra!
... code purement ludique...
Source / Exemple :
<?php
/*
CHINESE REMAINDER THEOREM
théorème des restes chinois
Résolution de l'équation
a = x mod m
b = x mod n
Condition initiale: gcd(m,n) = 1
function crt($a,$m,$b,$n){
$res = ($a*$n*eea($n,$m)+$b*$m*eea($m,$n))%($m*$n);
if ($res<0){
while ($res<0)
$res += $m*$n;
}
return $res;
}
// extended Euclid Algorithm pour le calcul de l'inverse
function eea($a,$b){
$x = array($a,1,0);
$y = array($b,0,1);
while ($y[0] > 0){
$rq = ed($x[0],$y[0]);
$temp = $x;
$x = $y;
$y[0] = $temp[0] - $rq[1]*$y[0];
$y[1] = $temp[1] - $rq[1]*$y[1];
$y[2] = $temp[2] - $rq[1]*$y[2];
}
return $x[1];
}
// division euclidienne
function ed($x,$y){
$rq[0] = $x % $y;
$rq[1] = ($x-$rq[0])/$y;
return $rq;
}
/*
3 = x mod 5
4 = x mod 7
=> x = 18
echo $res = crt(3,5,4,7); // $res = 18
?>
Vous n'êtes pas encore membre ?
inscrivez-vous, c'est gratuit et ça prend moins d'une minute !
Les membres obtiennent plus de réponses que les utilisateurs anonymes.
Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.
Le fait d'être membre vous permet d'avoir des options supplémentaires.