- /* 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";
- }
/* 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";
}