begin process at 2012 02 13 01:12:07
  Trouver un code source :
 
dans
 
[ Dernières recherches ]
Accueil > 

Code

 > 

Maths & Algorithmes

 > 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


 Information sur la source

Note :
8,33 / 10 - par 3 personnes
8,33 / 10

  • 1

  • 2

  • 3

  • 4

  • 5

  • 6

  • 7

  • 8

  • 9

  • 10
Catégorie :Maths & Algorithmes Niveau :Débutant Date de création :06/03/2004 Vu / téléchargé :13 381 / 316
Auteur : MetalDwarf

Ecrire un message privé
Commentaire sur cette source (40)
Ajouter un commentaire et/ou une note

 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

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

 Conclusion

Ce programme a ete teste sous Linux mais doit fonctionner sous windows (j ai teste un autre programme avec la NTL sous windows).

 Fichier Zip

Les Membres Club peuvent télécharger directement un fichier contenu dans le zip sans télécharger le zip en entier !

Télécharger le zip


 Sources du même auteur

Source avec Zip LECTURE/ECRITURE DES MSR (MODEL SPECIFIC REGISTER) EN C SOUS...
Source avec Zip Source avec une capture SOLUTION GRAPHIQUE APPROCHÉE AU PROBLÈME DES N CORPS
Source avec Zip Source avec une capture SERVEUR DE CHAT MULTITHREADE EN C SOUS LINUX
COMMENT UN PC FAIT DES MULTIPLICATIONS...
Source avec Zip COMPRESSION BZ2 (MIEUX QUE ZLIB) EN C.
Toutes les sources de MetalDwarf

 Sources de la même categorie

Source avec Zip UN EXAMPLE D'APPLICATION EN CUDA DE L'ALGORITHME DE SCAN POU... par oguzaras
Source avec Zip Source avec une capture CHIFFREMENT DE VIGENERE par lajouad
Source avec Zip Source avec une capture ANALYSE SYNTAXIQUE par lajouad
Source avec Zip Source avec une capture STRUCTURE D'UNE MATRICE PAR LES LISTE LINÉAIRE (NON CONTUGUS... par benzarabel
Source avec Zip Source avec une capture DESSINER UNE ARBRE BINAIRE( MODE CONSOLE): par benzarabel
Toutes les sources de la catégorie Maths & Algorithmes

Commentaires et avis

Commentaire de JCDjcd le 07/03/2004 10:33:34

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 ...)

Commentaire de Kirua le 07/03/2004 13:18:23

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?)

Commentaire de sibi12 le 07/03/2004 14:39:25

kirua &gt;
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...

@+

Commentaire de Kirua le 07/03/2004 14:41:51

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++ :-/

Commentaire de MetalDwarf le 07/03/2004 17:51:33

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.

Commentaire de Super_Mat le 01/10/2004 13:25:38

Dans ton code, tu dis :

tmp = n - 1
q = tmp

while(!(q % 2))     // on cherche t, nb de fois que 2 divise n

Or, t = nb de fois que 2 divise q, c-a-d  t = nb de fois que 2 divise tmp,  c-a-d  t = nb de fois que 2 divise n- 1

Or, n != n-1 donc il y a une faute soit dans le code, soit dans le commentaire.

Tu pourais vérifier ?


Commentaire de MetalDwarf le 01/10/2004 19:11:56

L erreur est dans le commentaire bien evidemment. Je voulais dire (n-1) et non n. C est assez clair parce qu on cherche a savoir si n est premier, et si il est premier et different de 2 alors il n est pas divisible par 2. Par contre pour (n-1) on a un nombre pair, donc qui est divisible (au moins une fois) par 2.
Je suis desole pour cette erreur.

Par contre pour l implementation je crois qu elle est correcte, car ce programme me donne les meme resultats que Maple.

Commentaire de ricezio le 07/10/2004 20:49:34

Je voudrais savoir:

power(num,2,3217);  // 2^3217 - 1 est premier...
num--;

Ca sert a quoi ? je comprend pas trop !

Merci d'avance

Commentaire de Super_Mat le 08/10/2004 14:28:43

Si tu lis bien, l'entrée de l'utilisateur est en commentaire, donc bloquée dans ce programme. Donc, le nombre qui est passé en paramètre est défini par le programme lui-même juste pour un essai.

power(num,2,3217);
num--;

calcule (2^3217)-1 .

Il calcule ce nombre car c'est un nombre très connu des mathématiciens : c'est un nombre de Mersenne (qui a l'avantage d'être grand : 969 chiffres) qui est premier. Donc normalement, le programme va répondre que ce nombre est premier.

Commentaire de MetalDwarf le 08/10/2004 16:20:16

Oui c est un des tests que j ai fait pour verifier la bonne implementation de l algorithme. D ailleurs pour la petite histoire j ai trouve ce nombre en utilisant maple sur un ordinateur en cours d info. Une simple petite boucle avec un test de primaute et c est parti (un petit conseil... prevoir du temps libre quand meme).

Et pour devancer une question potentielle, pour connaitre le nombre de chiffres d un nombre en base 10, il faut prendre la partie entiere plus 1 de log(nombre) avec log le logarithme decimal.

Commentaire de scelw le 15/12/2004 17:32:34

est-ce que ça n'irait pas plus vite si au lieu de diviser le nombre par deux, on regardait juste son dernier chiffre pour voir s'il est pair ou impair ? c'est possible d'utiliser des fonctions comme right() avec des nombres ZZ ?

et est-ce qu'on pourrait pas aussi rajouter une condition (toujours dans le but de gagner du temps d'exécution) pour éliminer les nombres dont la somme des chiffres fait 9 (et qui dans ce cas là sont divisibles par 9)? De même, avec les chiffres terminés par 5 (qui sont divisibles par 5) ?

est-ce que ceci est réalisable avec NTL ??

merci!

Commentaire de sibi12 le 15/12/2004 17:44:18

Je pense que tu devrai regarder la représentation binaire des nombres. diviser par 2 reviens a faire un decalage vers la droite ce qui est on ne peux plus rapide et verifier qu'un nombre est pair est encore plus rapide vu qu'il s'agit de regarder le bit le plus faible.

pour faire ce que tu dis il faut convertir tes nombres en chaine ce qui est assez lourd.

Commentaire de scelw le 15/12/2004 17:55:06

je comprends pour les nombres pairs... mais pour les nombres divisibles par 9 ? et par 5 ? dans ces deux cas précis, n'est-il pas intéressant d'essayer de les éliminer avant d'effectuer le test de Miller-Rabin proprement dit ?

Commentaire de Kirua le 15/12/2004 18:00:10

en fait, si tu testes (avant Miller Rabin) la divisibilité par les nombres premiers inférieurs à un certain nombre (mettons 2000), tu couvres déjà bcp de nombres, puisque la probabilité pour un entier d'être formé par un des plus petits nombres premiers est très grande. ça t'évite des bricolage avec les testes "humains" de divisibilité (par 9, 4, 8, 2, 3, 6, 5, 10 ...). D'autant plus que parmis ces tests ne sont utils que 2, 3 et 3 (les autres sont composés).

Générer les nombres premiers entre 2 et 2000 ça va très très vite (crible d'ératosthène), et ça ne prend pas des masses de place (Pi(2000) vaut pas grand chose, je sais pas combien mais ça doit aller)

Commentaire de Kirua le 15/12/2004 18:01:39

2, 3, et 5, pardon.

Commentaire de MetalDwarf le 15/12/2004 18:08:04

Oui ca permet d accelerer l algorithme car tu elimine deja un tres grand nombre de possibilites si tu enleves tous ces nombres.
C est d ailleurs comme ca que les generateurs aleatoires de nombres premiers utilises dans les logiciels de crypatge (par exemple) fonctionnent.

Commentaire de Kirua le 15/12/2004 18:22:33

ah, si tu as des infos sur la génération de grands nombres premiers je suis prenneur. Parce que à part tester un intervalle d'entiers... enfin, il y a bien cette "règle" comme quoi les nombres de la forme 6k + 1 et 6k - 1 sont souvent premiers, mais je me demande si ça ne vaut pas que pour les "petits" entiers (5, 7, 11, 13, 17, 19, 23, 29, 31, 37...). De toute façon si toutes les clefs étaient de cette forme ce serait plus facile à casser, donc c'est peu probablement comme ça qu'ils font. Tu as des infos? Je parle pas du crible d'ératosthène, parce que au-delà de 10 000 000 000 (et faut déjà vachement bien s'y prendre!) on a plus de mémoire...

Commentaire de sibi12 le 15/12/2004 18:27:29

Une source comme celle ci a eu pas mal de commentaire et on parle de pas mal de chose qui tourne autour : http://www.vbfrance.com/code.aspx?ID=27662

hormis le code on parle de mersenne, fermat et d'autres

Commentaire de Kirua le 15/12/2004 18:34:35

Ben Mersenne je veux bien mais c'est toujours le même problème. Si tous les documents RSA sont protégés par une clef multiple de deux nb de Mersenne, ça casse toute la protection :/

je vais lire les commentaires, mci.

Commentaire de Super_Mat le 15/12/2004 19:57:00

Je ne suis pas sûr que si le RSA était construit à partir de Mersennes premiers ca se casserrait facilement.

A mon avis, le mieux est de partir d'un fermat, vérifier sa primalité et hop !

Commentaire de Kirua le 15/12/2004 20:01:40

ben, logiquement il y a bcp moins de nombres de Mersenne premiers que des nombres premiers ^^ Donc ipso facto la protection est énormément réduite, étant donné que la protection de RSA réside dans la difficulté à factoriser  une partie de la clef publique...

Commentaire de Super_Mat le 15/12/2004 20:51:51

Donc la seule façon de procéder pour que les premiers ne soient pas sélectionnés est :

1 - prendre un entier au hazard
2 - s'il n'est pas premier, aller à 1
3 - utiliser ce nombre


En se basant sur le fait que 2 est rapide, et donc que le fait de boucler un nombre indéterminé de fois n'est pas conséquent.

Exact ?

Commentaire de Kirua le 15/12/2004 20:55:08

ben c'est ma question: est-ce qu'il y a plus intelligent?? et mon idée de départ était plutôt de prendre un nombre au hasard, et s'il n'est pas premier de faire Nb++ et de tester celui-là... On évite une trop grosse par de chance (puisque potentiellement en prennant chaque fois au hasard ça peut prendre un temps infini, alors que comme on peut prouver (facilement) qu'il existe une infinité de nombre premiers, ou que tu te places au départ dans le corps des entiers, en faisant chaque fois +1 tu tomberas sur un premier à coup sûr en un nombre fini d'essais.

Commentaire de MetalDwarf le 15/12/2004 21:14:19

D apres ce que je sais et ce que j ai vu, c est effectivement comme ca que ca fonctionne. En tout cas c est comme ca que ca fonctionne dans la classe Biginteger de java qui peut etre utilisee pour tout ce qu on veut (en effet il faut lui passer en argument un generateur aleatoire donc avec un "bon" generateur aletaoire elle est "acceptable" pour du RSA par ex).

Un nombre de la longueur voulue est genere de facon aleatoire, et ensuite on teste si il est premier ou non avec d abord un crible simple (verifier la divisibilite par 2,3,5,7,11,...) puis par un algorithme probabiliste comme Miller-Rabin.

Je ne pense pas qu il existe de methode plus intelligente de recherche de grand nombre premier, car sinon la securite du systeme RSA (mais aussi DSA et d autres) serait affaiblie...

Mais si il s agit "simplement" de trouver un grand nombre premier "pour la beaute du geste" chercher un nombre de Mersenne doit etre payant.

Commentaire de Kirua le 15/12/2004 21:19:04

"Mais si il s agit "simplement" de trouver un grand nombre premier "pour la beaute du geste" chercher un nombre de Mersenne doit etre payant."

Et même rémunérateur! Il y a des sommes énormes à gagner pour les gens qui trouvent des nombres premiers plus grands que tous ceux déjà trouvés. Il y a même un programme du style Seti@home qui fait ça, et les 4-5 derniers vainqueurs d'une prime utilisaient ce programme. Je sais plus comment il s'appelle...

Commentaire de MetalDwarf le 15/12/2004 21:20:01

Pour plus d informations sur la generation de nombres premiers en Java voici un patch envoye au projet gcj (compilateur java faisant partie du projet GNU).
La syntaxe est un peu bizarre car c est un fichier patch, mais c est lisible:

http://gcc.gnu.org/ml/java-patches/2000-q1/msg00120.html

Commentaire de scelw le 06/01/2005 18:00:10

Il s'agit d'une question à propos du test de Miller-Rabin.
(>> http://cryptosec.lautre.net/article.php3?id_article=12 ...[b]à lire pour comprendre la suite![/b])
C'est l'un des tests les plus rapides qui existent au monde. Mais il possède un "goulot d'étranglement" qui limite malgré tout sa vitesse d'exécution dès lors que l'on veut tester des nombres de très grande taille (plus d'un million de chiffres) : le calcul de y = a^r mod n (voir lien donné ci-dessus).
Ma question est : pour diminuer sensiblement le temps d'exécution de ce test, serait-il possible de choisir a dans l'intervalle ]1 ; (n-1)/2[ , voire ]1 ; (n-1)/(10^1000)[ ??
Quelles répercussions sur le résultat ? La probabilité d'avoir un nombre premier est-elle fortement modifiée?

Commentaire de MetalDwarf le 08/01/2005 13:55:41

a mon avis si personne ne l'a fait, il y a bien une raison...

Commentaire de Super_Mat le 08/01/2005 14:27:34

A priori, on peut limiter le domaine de a, mais on prend alors un risque plus grand de pseudo-primalité : en effet, la propriété est absolue (donc on peut dire si n est premier ou pas) si on fait le test pour tout a dans [1,n]. En pratique, on se prend quelques a au hasard.

En limitant davantage le domaine de a, la probabilité qu'un nombre pseudo-premier soit découvert augmente car il n'y a aucune chance de scanner certains a (au contraire de [1,n] où tous les a potentiels sont susceptibles d'être scannés)

Commentaire de scelw le 08/01/2005 15:24:36

merci pour tes infos super_mat. ça me permet de voir plus clair dans les grandes lignes de l'algo...

est-ce qu'on peut limiter r aussi? car c'est surtout l'exposant qui augmente de manière exponentielle le temps des calculs... je sais que r est déduis du nombre de fois que 2 est multiple de (n-1). mais n'y aurait-il pas moyen de "truquer" cela sans pour autant rendre le test complétement invalide?

Commentaire de Super_Mat le 08/01/2005 17:44:02

Non, on ne peut pas jouer sur r sinon cela fausse complétement les résultats.

Mais a^b % c n'est pas si gourmand que ca en calcul ! Evidemment, si on fait

x = a^b;
x = x % c;

Ca peut prendre beaucoup de temps. Mais la fonction d'exponentiation modulaire est bcp plus rapide.

Commentaire de scelw le 08/01/2005 18:03:32

personnellement j'utilise la fonction powermod() de la la librairie NTL de Victor Shoup (www.shoup.net/ntl).
Est-ce que vous pourriez me dire si cette fonction utilise l'exponentiation modulaire? Car moi, ça met vraiment beaucoup de temps quand même... Il faut dire que je travaille avec des nombres d'un million de chiffres environ... (d'où mon besoin d'optimiser/accélerer le test de Miller-Rabin).

merci!

Commentaire de Super_Mat le 08/01/2005 20:37:20

Assurément, NTL fait une exponentiation modulaire avec powermod.

Mais c'est normal d'avoir une certaine lenteur avec des millions de chiffres. Aujourd'hui, on considère normal de tester la primalité de nombres de 150,200 chiffres. A partir de 1000 chiffres, on considère qu'il n'existe pas de méthode pratique, c'est à dire fournissant un résultat rapidement.

Mais évidement, avec une machine rapide ca reste possible. Pour avoir des résultats plus rapide, il vaut mieux utiliser le test des trois Indiens dont on parle souvent, mais il est dur à implémenter (je vais essayer un de ces 4)

Ce qui est important, c'est de prendre a sur tout le domaine et d'avoir un générateur pseudo-aléatoire efficace.

Commentaire de scelw le 08/01/2005 21:34:35

oui g déjà entendu parler de la découverte des trois indiens. pourquoi est-ce que cet algo est dur à implémenter?

"Ce qui est important, c'est de prendre a sur tout le domaine" ??? tu m'as dit plus haut qu'on pouvait limiter le domaine d'où a est tiré aléatoirement... ?

quelle est cette allusion à un générateur pseudo-aléatoire efficace? je ne comprends. je n'ai jamais utilisé un tel générateur.

Commentaire de Super_Mat le 08/01/2005 23:22:02

J'ai dit que c'était possible (le programme ne plantera pas) mais cela trahi le théorème qui se cache derrière l'algorithme,  à savoir "pour tout a = {2,...,n} etc"

Deja en ne prenant que quelques a sur ce domaine, on a des risques de se tromper, mais en plus en en prenant dans un ensemble inclu strictement dans le domaine, c'est encore moins bien. L'algorithme ne vaut alors plus rien du tout, et en tout cas le nombre de pseudo-premier va grandir très rapidement.

En ce qui concerne les pseudo-aléatoires, on les appelle pseudo car en réalité un ordinateur "de base" ne sait pas créer un nombre réellement aléatoire. a est pris pseudo-aléatoirement entre 2 et n à cette ligne :

a = RandomBnd(tmp-1) + 2; // nb aleatoire entre 2 et n

Il faut que l'ordinateur puisse trouver rapidement ce nombre aléatoire, sinon la vitesse de calcul tombe en chute libre ! D'où le problème de ma bibliothèque GN où toutes les fonctions aléa sont à revoir. Il faut de plus que ce générateur fournisse des résultats le plus aléatoires possible car s'il existe une corrélation forte entre les différents a, le test n'est plus équilibré statistiquement. (la probabilité est perturbée)

Commentaire de scelw le 09/01/2005 10:42:05

D'accord, merci bien...

Pourquoi est-ce que l'algo des trois indiens est dur à implémenter??

Commentaire de Super_Mat le 09/01/2005 12:38:34

L'algorithme parait simple, mais quand on regarde de près, on a

SI a , alors b ;

et la condition a peut avoir 20,30 lignes de conditions à vérifier ;-)

Si tu veux davantage de conversation, mon num ICQ : 281-692-688

Commentaire de scelw le 09/01/2005 13:59:25

je n'ai pas ICQ mais je serai intéressé par "davantage de conversation"... MSN Messenger c'est possible ? mon adresse est : jojo29118@hotmail.com

Commentaire de scelw le 07/05/2006 12:50:15

J'ai trouvé une méthode pour compresser encore le temps d'exécution du test de Miller-Rabin (test probabiliste et non déterministe mais qui a l'avantage d'être le plus rapide, d'être généraliste (les nombres à tester n'ont pas besoin d'être d'une forme particulière) et très fiable). Dans un post plus haut, j'ai identifié le goulot d'étranglement du test (le point qui consomme le plus de temps d'exécution) comme étant la ligne de calcul "y = a^r mod n". Or plutôt que de choisir a non pas entre 1 et n - 1 (au risque de tomber sur de très grands a), mais entre 1 et ln n (ce qui est un intervalle déjà beaucoup plus restreint, surtout pour de grands n).

Voir le très intéressant débat suivant (qui porte exactement sur cette question) : http://les-mathematiques.u-strasbg.fr/phorum/read.php?f=2&i=128589&t=128589

Commentaire de tagwin le 01/05/2007 13:43:13

Bonjour "MetalDwarf", je voudrais juste savoir un petit détail stp sur l'installation de la bibliotheque NTL C++ sous windows, je dois la compiler ou comment dois je faire??

merci

 Ajouter un commentaire

Nos sponsors


Sondage...

CalendriCode

Février 2012
LMMJVSD
  12345
6789101112
13141516171819
20212223242526
272829    

Consulter la suite du CalendriCode
 
Développement réalisé par Nicolas SOREL (Nix) avec l'aide de : Cyril DURAND et Emmanuel (EBArtSoft), Merci à Vincent pour ses précieux conseils.
CodeS-SourceS.com© Toute reproduction même partielle est interdite sauf accord écrit du Webmaster
CodeS-SourceS.com© est une marque déposée tous droits réservés

Google Coop CodeS-SourceS Google Coop CodeS-SourceS
Temps d'éxécution de la page : 1,888 sec (3)

Nous contacter | Annoncer sur CodeS-SourceS | Mentions légales
Outils Convertisseur VB/C# Snippets et scripts Outils en ligne La ToolBox
Communauté Programmation Photographie Technologie Newsgroups Emploi Forum Blogs
Guide d'achat Téléphonie mobile Image et son Informatique Bureautique Jeux vidéo
Logiciels Internet & Réseau Développement Market Android Jeux & Loisirs Graphisme Multimédia Sécurité Pilotes
Loisirs Cartes virtuelles Vidéos droles Jeux en ligne Géoguide AndroLib (Android Market)