Chinese remainder theorem

Soyez le premier à donner votre avis sur cette source.

Snippet vu 4 526 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

Messages postés
230
Date d'inscription
mardi 21 janvier 2003
Statut
Membre
Dernière intervention
15 mai 2008

Je me disait aussi ;-)
Messages postés
1154
Date d'inscription
mardi 9 septembre 2003
Statut
Membre
Dernière intervention
15 août 2009
14
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)
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 ???
Messages postés
514
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.