Generateur de nombres premiers

Commenter

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

S'inscrire maintenant

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.

Du même auteur (malik7934)