Accueil > > > GENERATEUR DE NOMBRES PREMIERS
 GENERATEUR DE NOMBRES PREMIERS
 Information sur la source
 Description
Ben c'est un générateur de nombres premiers utilisant le test de Miller-Rabin. A quoi ça sert? Bah... c'est our les amis de RSA par exemple ;o) ! Il n'est pas fait pour les grands nombres, comme les GMP par exemple !
 Source
- // ------------ formulaire pour appeler les fonctions
- <HTML><TITLE>Générateur de Nombres Premiers Miller-Rabin Test)</TITLE><HTML><BODY bgcolor="#CCDDEE">
- Cet algorithme permet de générer un nombre premier compris entre 2 puissance l et 2 puissance (l-1) ...<BR />
- <B> Les grands nombres ne sont pas supportés!</B><BR />
- <form action="genprime.php" method="POST">
- <P>
- Entrer l: <INPUT type="text" name="powerl">
- <INPUT type="submit" value="générer">
- </P></form></BODY></HTML>
-
- // ------------ genprime.php
-
- <?php
-
- function puissance($x,$y){
- $resultat=1;
- for ($i=0;$i<$y;$i++)
- $resultat *= $x;
- return $resultat;
- }
-
- function int2bin($n,$l){
- $i = 0;
- if ($l != 0){
- for ($j=0;$j<$l;$j++)
- $bin[$j] = 0;
- }
- while($n >= 1){
- if (bcmod($n,2) == 1) {$bin[$i] = 1; $n = ($n-1)/2;}
- else {$bin[$i] = 0; $n = $n/2;}
- $i++;
- }
-
- return $bin;
- }
-
- function puissanceBigNbr($a,$n,$e){ // calcul de a^e mod n
-
- $m = max($a,$n);
- $o = int2bin($m, 0);
- $l = count($o);
- $be = int2bin($e,$l);
-
- $x = 1; $y = $a;
- for ($i=0;$i<$l;$i++){
- if ($be[$i] == 1){$x = bcmod(($x*$y),($n));}
- $y = bcmod(($y*$y),($n));
- }
-
- return $x;
- }
-
- function millerTest($n,$k){
-
- if ($n <4) {return 0;}
- else{
- if (bcmod($n,2) == 0) {return -2;}
- else{
- $s=0;
- $n2 = $n-1;
- while (bcmod(($n2),2) == 0){
- $s++;
- $n2 /= 2;}
- $t = ($n-1)/(puissance(2,$s));
- $cpt=0;
-
- for ($j=0; $j<$k;$j++){
- mt_srand((double)microtime()*1000000);
- $b = mt_rand(1,($n-1));
- $x = puissanceBigNbr($b,$n,$t);
- $i = 0;
- if ($x != 1){
- while ($x != ($n-1)){
- $x = bcmod((puissance($x,2)),($n));
- $i++;
- if (($i == $s) || ($x == 1))
- return -1;
- }
- }
- $cpt++;
- }
- return $cpt;
- }
- }
- }
-
-
- $powerl = $_POST['powerl'];
- if (!(isset($powerl))) {echo "INSERER UN NOMBRE<BR>"; include('miller.php'); exit();}
- if (!(is_numeric($powerl))){echo "INSERER UN NOMBRE<BR>"; include('miller.php'); exit();}
-
- $down = puissance(2,($powerl-1));
- $up = puissance(2,$powerl);
-
- $k = 20;
-
- echo '<HTML><TITLE>Générateur de Nombres Premiers (Miller-Rabin Test)</TITLE><HTML><BODY bgcolor="#CCDDEE">';
- echo 'Ok... on cherche un nombre premier compris entre '.$down.' et '.$up.'.<BR /><BR />';
- echo 'Etape 1: choix d\'un nombre aléatoire dans entre '.$down.' et '.$up.':<BR />';
-
-
- mt_srand((double)microtime()*1000000); // ce générateur aléatoire ne l'est pas vraiment
- $n = mt_rand($down,$up); // une amélioration serait d'utiliser un RNG plus "éprouvé"...
-
- echo "Etape 2: test de primalité avec $k itérations: <BR /><BR />";
-
- $rd = millerTest($n,$k);
- $i=0;
- while (($rd == -1) || ($rd == -2)){
- echo "tirage aléatoire $i: $n n'est pas premier <BR />";
- mt_srand((double)microtime()*1000000);
- $n = mt_rand($down,$up);
- $i++;
- $rd = millerTest($n,$k);
- }
- $i++;
- if (($rd == 0) ||($rd == 20))
- echo "tirage aléatoire $i:<B> $n est un nombre premier</B><BR />";
- if (($rd != 0) && ($rd != -1) && ($rd != -2) && ($rd != 20))
- echo "tirage aléatoire $i:<B> $n a passer le test $rd fois sur $k</B><BR />";
-
- echo '</BODY></HTML>';
- ?>
// ------------ formulaire pour appeler les fonctions
<HTML><TITLE>Générateur de Nombres Premiers Miller-Rabin Test)</TITLE><HTML><BODY bgcolor="#CCDDEE">
Cet algorithme permet de générer un nombre premier compris entre 2 puissance l et 2 puissance (l-1) ...<BR />
<B> Les grands nombres ne sont pas supportés!</B><BR />
<form action="genprime.php" method="POST">
<P>
Entrer l: <INPUT type="text" name="powerl">
<INPUT type="submit" value="générer">
</P></form></BODY></HTML>
// ------------ genprime.php
<?php
function puissance($x,$y){
$resultat=1;
for ($i=0;$i<$y;$i++)
$resultat *= $x;
return $resultat;
}
function int2bin($n,$l){
$i = 0;
if ($l != 0){
for ($j=0;$j<$l;$j++)
$bin[$j] = 0;
}
while($n >= 1){
if (bcmod($n,2) == 1) {$bin[$i] = 1; $n = ($n-1)/2;}
else {$bin[$i] = 0; $n = $n/2;}
$i++;
}
return $bin;
}
function puissanceBigNbr($a,$n,$e){ // calcul de a^e mod n
$m = max($a,$n);
$o = int2bin($m, 0);
$l = count($o);
$be = int2bin($e,$l);
$x = 1; $y = $a;
for ($i=0;$i<$l;$i++){
if ($be[$i] == 1){$x = bcmod(($x*$y),($n));}
$y = bcmod(($y*$y),($n));
}
return $x;
}
function millerTest($n,$k){
if ($n <4) {return 0;}
else{
if (bcmod($n,2) == 0) {return -2;}
else{
$s=0;
$n2 = $n-1;
while (bcmod(($n2),2) == 0){
$s++;
$n2 /= 2;}
$t = ($n-1)/(puissance(2,$s));
$cpt=0;
for ($j=0; $j<$k;$j++){
mt_srand((double)microtime()*1000000);
$b = mt_rand(1,($n-1));
$x = puissanceBigNbr($b,$n,$t);
$i = 0;
if ($x != 1){
while ($x != ($n-1)){
$x = bcmod((puissance($x,2)),($n));
$i++;
if (($i == $s) || ($x == 1))
return -1;
}
}
$cpt++;
}
return $cpt;
}
}
}
$powerl = $_POST['powerl'];
if (!(isset($powerl))) {echo "INSERER UN NOMBRE<BR>"; include('miller.php'); exit();}
if (!(is_numeric($powerl))){echo "INSERER UN NOMBRE<BR>"; include('miller.php'); exit();}
$down = puissance(2,($powerl-1));
$up = puissance(2,$powerl);
$k = 20;
echo '<HTML><TITLE>Générateur de Nombres Premiers (Miller-Rabin Test)</TITLE><HTML><BODY bgcolor="#CCDDEE">';
echo 'Ok... on cherche un nombre premier compris entre '.$down.' et '.$up.'.<BR /><BR />';
echo 'Etape 1: choix d\'un nombre aléatoire dans entre '.$down.' et '.$up.':<BR />';
mt_srand((double)microtime()*1000000); // ce générateur aléatoire ne l'est pas vraiment
$n = mt_rand($down,$up); // une amélioration serait d'utiliser un RNG plus "éprouvé"...
echo "Etape 2: test de primalité avec $k itérations: <BR /><BR />";
$rd = millerTest($n,$k);
$i=0;
while (($rd == -1) || ($rd == -2)){
echo "tirage aléatoire $i: $n n'est pas premier <BR />";
mt_srand((double)microtime()*1000000);
$n = mt_rand($down,$up);
$i++;
$rd = millerTest($n,$k);
}
$i++;
if (($rd == 0) ||($rd == 20))
echo "tirage aléatoire $i:<B> $n est un nombre premier</B><BR />";
if (($rd != 0) && ($rd != -1) && ($rd != -2) && ($rd != 20))
echo "tirage aléatoire $i:<B> $n a passer le test $rd fois sur $k</B><BR />";
echo '</BODY></HTML>';
?>
 Conclusion
J'ai fait une batterie de tests et je crois que tout beigne... ceci dit, si quelqu'un trouve une erreur (genre un nombre premier ignoré ou un nombre non-premier considéré comme premier), je suis preneur!
Une dernière chose: le paramètre $k est ici à 20. Plus il est grand, plus le résultat est sûr (mais plus le temps de calcul est long!)
 Historique
- 21 janvier 2005 17:48:03 :
- Ajout de deux contrôles (isset, is_numeric)
 Sources du même auteur
 Sources de la même categorie
 Commentaires et avis
|
Derniers Blogs
 [WP7] DYNAMICALLY CHANGE STARTUP PAGE[WP7] DYNAMICALLY CHANGE STARTUP PAGE par KooKiz
Let's say that you want to allow the user to customize the startup page of your application. You can easily change the startup page by editing the 'NavigationPage' attribute in the manifest file. But the manifest cannot be modified once the applicatio...
Cliquez pour lire la suite de l'article par KooKiz SESSION SILVERLIGHT 5 3D : SLIDES ET DEMOSSESSION SILVERLIGHT 5 3D : SLIDES ET DEMOS par Groc
Durant les techdays, j'ai eu le plaisir d'animer une session sur Silverlight 5 et la 3D avec Simon Ferquel. Comme promis, voici nos slides et mes démos (celles avec le viper BSG) ici et là. Pour mémoire, les démos utilisent toutes le viper BSG...
Cliquez pour lire la suite de l'article par Groc [TECHDAYS 2012] SESSION WEBMATRIX 2 : LE COUTEAU SUISSE GRATUIT POUR VOS DéVELOPPEMENTS WEB - SLIDES[TECHDAYS 2012] SESSION WEBMATRIX 2 : LE COUTEAU SUISSE GRATUIT POUR VOS DéVELOPPEMENTS WEB - SLIDES par gpommier
Suite à la session que j'ai présenté sur WebMatrix 2, vous pouvez trouver les slides ici, ainsi que les démos en packages nuget : démos1 et démos2 J'en profite pour remercier chaleureusement tous ceux qui sont venus très nombreux à cette sess...
Cliquez pour lire la suite de l'article par gpommier [SHAREPOINT] LES SESSIONS TECHDAYS 2012.[SHAREPOINT] LES SESSIONS TECHDAYS 2012. par Patrick Guimonet
Voici donc pour ceux qui n'ont pas pu venir, ou ceux qui n'ont pas pu toutes les suivre la liste des sessions SharePoint aux TechDays 2012, que je mettrais à jour dès que les liens des vidéo seront disponibles. Ou ici : http...
Cliquez pour lire la suite de l'article par Patrick Guimonet TECHDAYS PARIS 2012 : SESSION PLEINIèRE JOUR 3TECHDAYS PARIS 2012 : SESSION PLEINIèRE JOUR 3 par ROMELARD Fabrice
Speaker: Bernard Ourghanlian Cette session est comme chaque jour transmise en live par BrainSonic, et j'ai donc suivi cette troisième pleinière par ce moyen sur mon iPad . Elle est dédiée comme chaque année à la mise en perspective de l'é...
Cliquez pour lire la suite de l'article par ROMELARD Fabrice
Forum
 RE : SONDAGE..RE : SONDAGE.. par phpAnonyme
Cliquez pour lire la suite par phpAnonyme RE : SONDAGE..RE : SONDAGE.. par TychoBrahe
Cliquez pour lire la suite par TychoBrahe
Logiciels
 Tribler (2012)TRIBLER (2012)Tribler est un client pair à pair (P2P/Peer-to-Peer) open source avec la capacité de regarder des... Cliquez pour télécharger Tribler OneSwarm (2012)ONESWARM (2012)Le peer-to-peer qui protège votre vie privée, c'est OneSwarm.
Ce logiciel de peer-to-peer crypté... Cliquez pour télécharger OneSwarm PONAMEDIA PREMIUM - HELLLOOO FLASH DEMO (V8.4)PONAMEDIA PREMIUM - HELLLOOO FLASH DEMO (V8.4)PONAMEDIA TV DEVIENS HELLLOOO FLASH
LA TV SUR VOTRE ORDINATEUR.
Toute une plateforme Multi... Cliquez pour télécharger PONAMEDIA PREMIUM - HELLLOOO FLASH DEMO Academy System (17.2.1.0)ACADEMY SYSTEM (17.2.1.0)Logiciel de gestion des établissements.
- élèves/étudiants (inscription, dossier, absence...)
-... Cliquez pour télécharger Academy System Easy-Planning (1.0.0.1)EASY-PLANNING (1.0.0.1)Basé sur les mêmes principes que MyPlanning, Easy-Planning permet de créer des plannings sous la ... Cliquez pour télécharger Easy-Planning
|