generateur de nombre premier

**hansaplast** · 28/04/2006, 14h15

voila mes algo, je paut aps encore les tester, je les corrigerait si jamais ils sont faux :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
/*
 * fait passer le test de miller  rabbin a la variable
 * <a href="http://fr.wikipedia.org/wiki/Test_de_primalit%C3%A9_de_Miller-Rabin" target="_blank">http://fr.wikipedia.org/wiki/Test_de...e_Miller-Rabin</a>
 */
bool encrypt::miller_rabbin(long n) //n doit toujours etre pair
{ 
 long d;
 d = n -1;
 long s;
 s = 0;
 while ( d % 2 == 0 ) {
  d = x/2; 
  s++;
 }
 //arrivé ici, on a :   n - 1 = 2^s * d
 //maintenant, on va tester k fois si le nombre est premier
 int k = 10;
 int aleatoire;
 long r;
 for (i = 0; i < k; i++) {
  //on prend un nombre aléatoire compris entre 1 et var-1 
  aleatoire = rand() % ( n - 1 );
  if ( pow(aleatoire, d) % n != 1 )
   return false;
  for (r = 0; r < s; r++) {
   if ( pox(aleatoire, ( 2 * r * d ) ) % n != -1)
    return false;
  }  
 }
 //si le chiffre a passé tous les tests, alors i l est probablement premier.
 return true;  
}
/*
 * fait passer le test de primalitée de fermat
 * <a href="http://fr.wikipedia.org/wiki/Test_de_primalit%C3%A9_de_Fermat" target="_blank">http://fr.wikipedia.org/wiki/Test_de...3%A9_de_Fermat</a>
 */
bool encrypt::Fermat(long n)
{
  int tabPrem[4];
  tabPrem[0] = 1;
  tabPrem[1] = pow(2, n - 1);
  tabPrem[2] = pow(3, n - 1);
  tabPrem[3] = pow(5, n - 1);
  tabPrem[4] = pow(7, n - 1);
 
  int i, j;
  int x;
  for (i = 0; i < 5; i++) {  // on  parcouir le tableau tabPrem
   x = 0;
  while ( tabPrem[i] > x ) {
   if ( tabPrem[i] == x*n ) { 
    break;
   x++;
  }
  if ( x != 1 )
   return false;
  }
  //si le chiffre a passé tous les tests, alors on peut renvoyer vrai => il est probablement premier.
  return true;  
}

**Sivrît** · 28/04/2006, 14h37

Envoyé par j.p.mignot

Dans mon code j'initialise
j=0;
k=1;ce qui est juste.
j=0 car le 1er nombre premier déclaré est 2
(premier[0]=2) est les nombres paires sont évincés de la recherche
( raison de k += 2)
on donne premier[1]=3 pour que la boucle commence correctement. <si non la 1er itération invoque un rang non encore calculé> Cela doit être innutile si on limite non pas a k2= sqrt(k) +1 comme je l'ai fait par pridence mais à la vraie limite k2=Trunc( sqrt(k)).
Pour le reste le code tourne correctement. Vérifiez vous-même!
à chaque valeur de i on teste au plus le nommbre de nombre premiers < sqrt(i) ce qui n'est pas énorme. Bien sur je ne dis pas que cela soit parfait!
Sur mon PC trouver tous les nombres 1er <= 10'000 prends entre 0.5 et 1 sec.

Justement, je viens de vérifier pour être certain de ce que je dis et la sortie est comme je le pensais :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

Le problème est que l'on commence les comparaisons avec premier[1] (normal, tester la parité est inutile) et que la boucle est exécutée au moins une fois. La première itération divise donc 3 par 3, c'est pas premier on continue... sans incrémenter j. On trouve ensuite 5 premier, j passe à 1 et premier[1] devient 5. A partir de là les multiple de 3 ne sont plus éliminés.

On a au moins besoin de commencer avec j=1, ou alors il faut un while standard pour la boucle interne. Et autant partir avec k=3, comme ça on teste de suite 5 mais je chipotte.

**hansaplast** · 28/04/2006, 14h58

arf, encore un pb :
http://fr.wikipedia.org/wiki/Rivest_Shamir_Adleman

que signifie ce genre de notation :

1 (mod (x) )

le mod(x) ici signifie quoi? pas modulo quand meme?

**zul** · 28/04/2006, 16h53

SI 1 mod x, c'est bien modulo X. En particulier

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
 
a = 1 mod x signifie Il existe n entier tel que a = n*x + 1 
autre notation : a = 1[x]

( vivement la balise latex ).

Pour l'implémentation de tes algos quelques petits trucs me chiffonent

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
 
while ( d % 2 == 0 ) {
  d = x/2; 
  s++;
 }

D'ou vient ce x ? je suppose qu'il s'agit de d

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
 
aleatoire = rand() % ( n - 1 );

cela génére un nombre entre 0 et n-2. Il faut rajouter 1 si tu veux assurer l'intervalle [1,n-1]

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
 
if ( pow(aleatoire, d) % n != 1 )

C'est correct en tant qu'algorithme naif, mais je crians que ca ne marche aps bien en realité ( précision des doubles, enorme calcul à faire ). Implémente plutot une exponentiation modulaire ( http://fr.wikipedia.org/wiki/Exponentiation_modulaire ).
Cela te sera de toute facon utile pour tous les calculs sur les entiers modulo quelquechose.

**j.p.mignot** · 28/04/2006, 17h12

Effectivement un bug dans le sof. désolé...
la correction donne

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
 
   premier[0]=2;
   premier[1]=3;
   j=1;
   k=3;

je corrige le post d'origine.
merci d'avoir signlé cette erreur d'initialisation
sivrit note

mais je chipotte

ce n'est pas vrai! il y avait un bug ruinant le résultat!

**hansaplast** · 28/04/2006, 18h51

merci zul, je prend note

ps : le x, ca doit etre ca, j'ai renommé mes variables pour etre en coprrespondance avec celles données dans wikipedia

**hansaplast** · 29/05/2006, 09h30

je rajoute un lien vers un site decrivant la norme ANSI X9

http://www.rsasecurity.com/rsalabs/node.asp?id=2306

j'ai pas tout lut, mais, y'a des choses interressantes comme ca par exemple

edit : correction du lien :'(

**droggo** · 24/04/2008, 18h27

Gia,

Envoyé par hansaplast

lol, c'est pour une action de BTS, les profs n'y verrons que du feu, et, surtout, je rpesenterait mon soft sur un celeron... qui rame sous win 98 (et qui a deja ete reformaté 4 fois depuis le debut de l'année scholaire...)

Arrête de prendre tes profs pour des billes, et tu feras du travail un peu plus sérieux, ce qui te conduira à mieux comprendre ce que tu fais, et pourquoi.

Au passage, un effort sur l'orthographe ne ferait de mal à personne.