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

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

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)