Generateur de nombres premiers

Soyez le premier à donner votre avis sur cette source.

Snippet vu 12 258 fois - Téléchargée 30 fois

Contenu du snippet

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 / Exemple :


// ------------ 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!)

A voir également

Ajouter un commentaire

Commentaires

cs_Anthomicro
Messages postés
9433
Date d'inscription
mardi 9 octobre 2001
Statut
Membre
Dernière intervention
13 avril 2007
8 -
Salut,

bon tu t'en doutais, le code html est crade...

Mais je n'ai pas envie de corriger, puisque tu as fait exprès de poster cette source sous cette forme.

Les echo sont aussi crades au passage, et tu ne vérifies nul part avec isset() si les variables $_POST sont présentes...
malik7934
Messages postés
1162
Date d'inscription
mardi 9 septembre 2003
Statut
Membre
Dernière intervention
15 août 2009
2 -
Tu rigoles! J'ai bien fait gaffe de mettre des / dans
et d'utiliser des que tu utilises et moi jamais... par contre les echos, c'est vrai que j'ai brassé... mais #*&#* à la fin! Le but de ce code, c'est de présenter des fonctions... pas un affichage!

Un point pour toi par contre: je n'utilise jamais isset(), mais je devrais... je vais corriger...
cs_Anthomicro
Messages postés
9433
Date d'inscription
mardi 9 octobre 2001
Statut
Membre
Dernière intervention
13 avril 2007
8 -
non les balises sont crades, elles doivent être en minuscules...
malik7934
Messages postés
1162
Date d'inscription
mardi 9 septembre 2003
Statut
Membre
Dernière intervention
15 août 2009
2 -
"elles doivent être en minuscules"... ok, je m'étais rangé à ton avis mais là je laisse tomber. Tu devrais regarder le travail derrière le 'XHTML-W3C-RFC-ement' correct de temps en temps au lieu de te braquer sur le '/' qui manque ou la majuscule qui va pas...

J'hallucine...
cs_Anthomicro
Messages postés
9433
Date d'inscription
mardi 9 octobre 2001
Statut
Membre
Dernière intervention
13 avril 2007
8 -
Mais le problème est que ce n'est pas correct justement...

Après suis mon avis ou pas, perso je m'en fiche après tout, j'aurais fait mon devoir. Le seul truc à ne pas faire c'est, lorsque tu réponds à quelqu'un, de coder comme tu le fais actuellement, c'est tout...

Que tu codes comme un porc c'est un fait, mais ne codes pas comme un porc lorsque tu veux rendre service à la communauté puisque c'est l'effet inverse qui se produira à plus ou moins long terme, et après on sera toujours obligés de rabacher "en minuscules ceci, <?php au lieu de <?" à cause de gens comme toi...

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.