Chinese remainder theorem

Soyez le premier à donner votre avis sur cette source.

Snippet vu 4 418 fois - Téléchargée 33 fois

Contenu du snippet

"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 ?>

A voir également

Ajouter un commentaire

Commentaires

cs_dominion
Messages postés
230
Date d'inscription
mardi 21 janvier 2003
Statut
Membre
Dernière intervention
15 mai 2008
-
Je me disait aussi ;-)
malik7934
Messages postés
1162
Date d'inscription
mardi 9 septembre 2003
Statut
Membre
Dernière intervention
15 août 2009
2 -
Non, pas spécialement. Un code pour RSA ce serait plutôt un générateur de nombre premier.

Ceci dit, le CRT est effectivement utile dans certaines attaques contre RSA ;o)
cs_dominion
Messages postés
230
Date d'inscription
mardi 21 janvier 2003
Statut
Membre
Dernière intervention
15 mai 2008
-
Ca ne serais pas un code pour RSA ca ???
LocalStone
Messages postés
515
Date d'inscription
mercredi 19 mars 2003
Statut
Membre
Dernière intervention
1 mars 2009
-
Hé hé hé hé ... 8/10.

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.