1. Accueil
  2. C / C++ / C++.NET
  3. Sources C / C++ / C++.NET
  4. Sources Maths & Algorithmes
  5. Teste si un tres grand nombre (plusieurs milliers de chiffres) est premier avec ntl et miller-rabin

Teste si un tres grand nombre (plusieurs milliers de chiffres) est premier avec ntl et miller-rabin

Soyez le premier à donner votre avis sur cette source.

Vue 17 250 fois - Téléchargée 409 fois

Télécharger le projet
Commenter

Description

Juste une petite implementation de l'algorithme de Miller-Rabin en C++ avec NTL. NTL est une bibliotheque C++ qui permet de manipuler de tres grand nombres (je ne sais meme pas si il y a une limite) et de faire des operations dessus (les operrateurs ont ete redefinis et bien d autres encore...).
L'algorithme de Miller-Rabin est un algorithme probabiliste, qui ne permet pas de prouver qu un nombre est premier ou compose mais de le dire avec une TRES faible incertitude. Il est utilise dans tous les systemes ayant besoin de GRANDS nombres premiers (RSA par exemple...).

Pour le compiler il faut NTL qui se trouve ici : www.shoup.net/ntl
Cette librairie se compile sans mal sous Linux ou VC++.

Source / Exemple : 


/* Ce programme donne un "avis" sur la primalite


     
  •  d'un nombre meme tres grand en utilisant l'algorithme

    •  
  •  de Miller-Rabin et la bibliotheque NTL (www.shoup.net/ntl)

 *


     
  •  Compile sous Linux avec g++ -lntl isprime.cpp -o isprime

    •  
  •  Devrait passer sous windows avec la librairie NTL

    •  
  • /


#include <NTL/ZZ.h>
#include <iostream>

/* 1er argument : le nombre a tester
   2e  argument : le nombre de tours de boucles a effectuer
                  + il est grand + la fiabilite est grande 
                  mais + le temps de calcul aussi! */
int isprime(ZZ n, int nb_test = 20)
{
  ZZ q,p,a,b;
  ZZ tmp = n-1;
  int t = 0;
  int e = 0;
   
  if(!(n%2)) return 0; // divisible par 2
  
  q = tmp;
  while(!(q % 2))      // on cherche t, nb de fois que 2 divise n
    {
      t++;
      q = q / 2;
    }
  for(int i=0;i<nb_test;i++)
    {
      a = RandomBnd(tmp-1) + 2; // nb aleatoire entre 2 et n
      e = 0;
      b = PowerMod(a, q, n);   // b = a^q mod n
      if(b!=1)
	{
	  while((b!=1) && (b!=(n-1)) && (e<(t-1)))
	    {
	      e = e + 1;
	      b = SqrMod(b, n); // b = a^2 mod n
	    }
	  if(b!=tmp) return 0;  // compose
	}
    }
  return 1; // peut-etre premier
}

int main(int argc, char **argv)
{
  ZZ num;
  // cout << "Entrez un nombre a tester :";
  // cin >> num;
  power(num,2,3217);  // 2^3217 - 1 est premier...
  num--;
  if(isprime(num)) cout << "\nPeut-etre premier.\n";
  else cout << "\nCompose\n";
  cout << num << "\n";
}

Conclusion :


Ce programme a ete teste sous Linux mais doit fonctionner sous windows (j ai teste un autre programme avec la NTL sous windows).
Télécharger le projet

Codes Sources

A voir également

Ajouter un commentaire Commentaires
cs_JCDjcd Messages postés 1138 Date d'inscription mardi 10 juin 2003 Statut Membre Dernière intervention 25 janvier 2009 4
7 mars 2004 à 10:33
Pour quoi tu utilise la librairie NTL, ici tu n'a en fait rien fait de nouveau. Mois en premiere j'ai fais une TPE sur le RSA, et j'ai du aussi faire l'algorithme de Miller-Rabin, mais j'ai programmer moi meme les "PowerMod" & Co.

Programmer "PowerMod" est tres interessante, car il fuat que ce soit rapide avec des puissance tres grande. L'algotrihme utilisé est plus interrseant en soit, que le teste de primalite de Miller-Rabin.
D'aileurs je vien d'aller voir dans la librairie NTL, qu'il utilise cet algorithme.


c'est koi ce "int isprime(ZZ n, int nb_test 20)" ????20 dans la declaration de la fonction ! Bon sinon tu peux dire la probabilite d'erreur, qui est de (1/4)^20 ici, donc tres negligeable (enfin je crois que c'est ca, a verifier ...)
cs_Kirua Messages postés 3006 Date d'inscription dimanche 14 avril 2002 Statut Membre Dernière intervention 31 décembre 2008
7 mars 2004 à 13:18
if(!(n%2)) return 0; // divisible par 2

tu peux faire n&1 je pense, j'ai lu ça il y a peu sur cppfrance. le principe c'est de vérifier juste le dernier bit, puisqu'il vaut 1 s'il est activé, et s'il n'est pas activé on a forcément un nb paire. c plus rapide de faire des opérations sur les bits qu'un modulo :-)
(faut qd même vérifier que c bien x&1...)

jvais me renseigner sur miller-rabin (euh, c'est deux types en fait?)
sibi12 Messages postés 337 Date d'inscription jeudi 19 décembre 2002 Statut Membre Dernière intervention 15 avril 2006
7 mars 2004 à 14:39
kirua >
Oui, Miller et Rabin sont 2 personnes differentes.

Miller-Rabin est le test de primalité le plus rapide sur de grand nombre. Il lui faut en argument un nombre aléatoire avec lequel il effectue toute une série d'opération (voir plus haut).

on l'utilise énormémént en cryptographie même si ce test n'est pas decisif.c'est à dire que si le test est negatif, le nombre n'est pas premier sinon il ne donne qu'une probabilité que ce nombre soit premier.

en répetant ce test plusieur fois avec un nombre premier et comme argument un nombre aléatoire différent a chaque fois, on tend très vite vers une probabilité égale à un

Un algo interressant également est celui des 3 indiens mais il est assez difficile à coder...

@+
cs_Kirua Messages postés 3006 Date d'inscription dimanche 14 avril 2002 Statut Membre Dernière intervention 31 décembre 2008
7 mars 2004 à 14:41
ouais j'ai lu l'article ds le science et vie hors série sur les nb premiers, mais c t y a un moment. ils parlaient des 3 indiens.
ils parlaient d'un algo de 11 (ou 13 sans plus) lignes, mais rien que la première condition (sur une ligne) demanderait plusieurs dizaines de lignes en C++ :-/
MetalDwarf Messages postés 241 Date d'inscription mardi 29 octobre 2002 Statut Membre Dernière intervention 23 janvier 2006
7 mars 2004 à 17:51
Pour repondre a JCDjcd c est vrai qu il n y a pas grand chose de nouveau dans ce code mais j ai decouvert l algorithme de Miller-Rabin il y a peu parce que je cherchais a voir si de tres grands nombres etaient premiers et j ai trouve interessant de le mettre ici.
Pour ce qui est de la gestion des grands nombres j ai une idee de la methode, surtout pour le PowerMod (exponentiation modulaire rapide...) car j ai lu un article qui traite des difficultes d implementation de RSA, et donc de cet algo mais je n ai pas eu le temps de le programmer. En plus NTL fait ca bien mieux (et BEAUCOUP mieux que maple 8...) et ca permet de voir sommairement comment marche cette bibliotheque.
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 (MetalDwarf)