Generateur de nombres premiers

Soyez le premier à donner votre avis sur cette source.

Snippet vu 12 542 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

Messages postés
3006
Date d'inscription
dimanche 14 avril 2002
Statut
Membre
Dernière intervention
31 décembre 2008

Yup, à dans un mois :). Et si tout va bien, il y aura même une team coder-studio avec T-shirts ^_^.
Messages postés
12303
Date d'inscription
mardi 10 février 2004
Statut
Modérateur
Dernière intervention
30 juillet 2012
36
kirua> ouais, on voit des ups tout les ans ici :) congratulation pour prologin, on se voit dans un mois :)
Messages postés
21
Date d'inscription
jeudi 2 janvier 2003
Statut
Membre
Dernière intervention
19 mars 2007

Pas mal ca ma servi un peu
Ton code est tres bien et te laisse pas deboussoller par des br**** avec des commantaire decalés
Messages postés
3006
Date d'inscription
dimanche 14 avril 2002
Statut
Membre
Dernière intervention
31 décembre 2008

Ca fait même plus d'un an cette phrase-là ^^.
Messages postés
2
Date d'inscription
jeudi 4 novembre 2004
Statut
Membre
Dernière intervention
8 mai 2007

[4 mois après]
"C'est compliqué d'agir avec l'infini... faut voir comment on le défini." ^_^...
Afficher les 65 commentaires

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.