Discussion :

[hansaplast]

Bonjours, je voudrait savoir si vous connaissiez un algo assez simple de generation de nombre premier?

je travaille en c++, et je suis...
pas tres bon :'(

donc, si l'algo etait pas trop complexe ce serait le must!

je veut faire cet algo afin d'implementer mon propre protocole d'encryptage (clef Pub / Priv), qui n'a d'autre ambition que d'exister, merci

[j.p.mignot]

On trouve des fonctions générant les nombres premiers sur
http://fr.wikipedia.org/wiki/Nombre_premier

[gangsoleil]

Bonjour,

Tu souhaites générer un nombre premier... Est-ce que tu souhaites par exemple écrire une méthode qui prenne en entré un nombre, et qui retourne le plus petit nombre premier supérieur ?

A moins que tu n'aies autre chose en tête ?

[hansaplast]

en fait, mon but est tout bete : generer deux nombres premiers, afin de créer une connexion securisée par clef publique / clef privée.

ceci pour une action de BTS, donc je ne cherche pas un entier trop grand ni quoi que ce soit, just eun petit algo assez simpple

ou sinon, j'avait lut un topic parlant de generer deux nombres premier a partir d'un hash MD5 d'un mot de passe, ca me conviendrait aussi, mais je vait deja aller voir du coté du wiki, merci

si j'ai bien compris :

f(n) = 2 + (2n! mod (n + 1))

est une formule generant un premeir pour 0 < n < 40

c'est bien ca? ca me conviendrait.... (po tres exigent le type lol ^^)

[thewho]

si j'ai bien compris :

Code :

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

f(n) = 2 + (2n! mod (n + 1))

est une formule generant un premeir pour 0 < n < 40

c'est bien ca? ca me conviendrait.... (po tres exigent le type lol ^^)

Si tu te contentes de ça, tu n'es effectivement pas exigeant !!
Et à ce niveau là, autant les faire à la main.

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

donc, je ne susi pas exigent, et je pense que c'est pas plus mal, lol...

apres, si tu genere un nombre premier tres grand, certes, c'est tres long, mais surtout, il faut le stocker, tu ne va pas le recalculer a chazque fois... et là... j'ai pas le temps de securiser ce stockag, donc... hop hop hop! calculé a la volée

sinon, a voir (s'apres un non erudit en maths) : http://fr.wikipedia.org/wiki/Test_de_primalit%C3%A9_AKS

ps : je suis repneur de toute formule pas trop gourmande en ressource

[ToTo13]

Bonjour,

dans les cours de cryptographie, il existe des méthodes probabilistes qui te donne la probabilité qu'un nombre ne soit pas premier.
Ces méthodes sont extrèmement simples et robuste.

[zul]

Je te deconseille la méthode deterministe car la complexité de l'algorithme ainsi que la complexité d'implémentation sont grandes.

En général, en cryptographie, on génére un grand nombre aleatoire, et on lui fait passer successivment le test de primalité de Fermet et celui de Miller-Rabbin. Si les deux tests passent ( cad ils ne renvoient pas : ceci est un nombr composé ), il y'a une forte probabilité que ce nombre soit premier.

Il y'a finalement très peu de temps que l'on peut determiniser si un grand nombre quelconque est premier et cela reste très couteux en général.

[hansaplast]

Je te deconseille la méthode deterministe car la complexité de l'algorithme ainsi que la complexité d'implémentation sont grandes.

En général, en cryptographie, on génére un grand nombre aleatoire, et on lui fait passer successivment le test de primalité de Fermet et celui de Miller-Rabbin. Si les deux tests passent ( cad ils ne renvoient pas : ceci est un nombr composé ), il y'a une forte probabilité que ce nombre soit premier.

Il y'a finalement très peu de temps que l'on peut determiniser si un grand nombre quelconque est premier et cela reste très couteux en général.

pour le test de miller-rabbin, il faut tester x fois si le nombre est premier, + x est grand, plus le test est fiable, d'apres vous, je doit prendre quellle valeure pour x (combien de tests?)


sinon, pour m'aider dans la comprehension des aticles de wikipedia : svp que sigifie un triple egale?
_
=

?

merci

[Jedai]

Le "triple égal" traduit souvent une relation d'équivalence, dans ton cas, il s'agit d'une équivalence à modulo p (le nombre entre parenthèse à la fin de l'expression), c'est à dire que les deux nombres de part et d'autres du triple égal ont le même reste dans la division euclidienne par p. Les opérations à modulo sont extrèmement importante en algèbre, donc tu ferais mieux de t'y habituer.

--
Jedaï

[ToTo13]

Bonjour,

le triple égal est ce que l'on appelle une relation de congruence, comme marqué précédemment.
un petit exemple (le égal est un triple égal) :
5 = 2 (3) parce que 5 = 2+3n, ici n=1
17 = 5 (6) <=> 17 = 5+6n, ici n=2

Pour ce qui est d'évaluer x, nombre de fois qu'il faut faire le test. Tout dépend de la vitesse de convergence du test.
Beaucoup de test on une convergence exponentielle du style : si on fait n fois le test, alors il y a une chance sur deux puissance n que le nombre ne soit pas premier.
Il te faut donc regarder la convergence des test afin de savoir combien de fois il faut le répéter pour que la probabilité soit assez faible.

[hansaplast]

merci, une derniere question, avec celle du test de miller-rabbin :

la facon la plus logique de proceder est de prendre un impair X aleatoire, et de le decrementer de 2 a chaque fois que les tests echouent? (je me doute que oui,mais bon...)


donc ca donne

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
X = aleatoire();
estPasPremier = vrai;
tant que (estPasPremeir) {
    si (Miller_rabbin(x) ) 
        x = Fermat(x);
}
renvoyer x
 
 
----------------------------
fonction miller_rabbin(int x) {
  int s = 0;
 
   tant que (x % 2 ==0  &&  x > 0) {
        x -= 2;
        s++;
    }
   //x = 2^s *1
 
 
}

et la, je bloque, car dnas la formule, ils disent :

écrire n − 1 comme 2s × d en factorisant les puissances de 2 à partir de n − 1

ors, selon moi (je sait que j'ai tort), d sera toujours egal a 1...
facoriser un nombre pair par ses puissance de 2 sera toujours finit...
ou ais-je tort???

[hansaplast]

je susi desolé, mais je met un petit "up" car je n'ai plus qu'une semaine avant mes exams, et j'aurait bien aimé implementer ceci...

[j.p.mignot]

le petit code suivant doit générer la listes de tous les nombres 1er <= i.
ils vont de premier[0] à premier[j]
( sauf si on arrive en limitation du tableau bien entendu !! )

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
 
 
#include "Math.h"
void pr_lst(int  i )
   {
   const mx = 2500;
   int  premier[mx];
   int k,j,l,k2;
   bool ok;
   premier[0]=2;
   premier[1]=3;
   j=1; // et non 0 
   k=3; // et non 1
   do
      {
      k += 2;
      k2= (int)(sqrt(k))+1;
      l=0;
      ok=false;
      do
         {
         l++;
         ok = ok || (( k % premier[l]) == 0);
         if (ok) l = j+1;
         } while (( l < j) && ( premier[l] < k2));
      if ( !ok)
         premier[++j] = k;
      if ( j== mx-1) k=i+1;
      } while ( k <= i);
   }

[hansaplast]

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
#include "Math.h"
void pr_lst(int  i )
   {
   const mx = 2500;
   int  premier[mx];
   int k,j,l,k2;
   bool ok;
   premier[0]=2;
   premier[1]=3;
   j=0;
   k=1;
   do
      {
      k += 2;
      k2= (int)(sqrt(k))+1;
      l=0;
      ok=false;
      do {
         l++;  
         ok = ok || (( k % premier[l]) == 0);
         if (ok) 
               l = j+1;
      } while (( l < j) && ( premier[l] < k2));
      if ( !ok)
         premier[++j] = k;
      if ( j== mx-1) k=i+1;
   } while ( k <= i);
 
   }

donc, pour trouver les premier, tu parcours le tableau de nombres premiers inferieurs tant que la valeur est < a la racine => mais pourquoi a tu 2 incrementation de l? ne risque t on pas de sauter quelques valeurs?
ensuite, pourquoi un

Code :

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

if ( !ok)

? ne faudrait il pas un

Code :

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

if ( ok)

?
ton dernier if, pas de pb

[Sivrît]

Je me permet de remarquer que dans le code de j.p.mignot il faudrait initialiser avec

Code :

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

1
2
3
 
j=1; // Dernier index utilisé de 'premier'
k=3; // Dernier nombre traité, donc 3 que l'on a déjà placé dans 'premier'

Le 'ok' est bon car il veut dire 'est divisible', donc on ne garde le nombre k que si l'on n'a pas trouvé de diviseur.

Mais le défaut du crible d'Eratostène est qu'en crypto on a besoin de très grands nombres premiers, ce qui va demander beaucoup de calculs et trop de mémoire. Mais comme hansaplast ne veut pas de nombres à deux milles chiffres ça suffira peut-être...

[hansaplast]

arf, c chiant d'etre chiant...
depuis que j'ai vut les algo de miller-rabin et consoeurs...
j'aimerait bien les implementer, mais :

et la, je bloque, car dnas la formule, ils disent :

Citation:
écrire n − 1 comme 2s × d en factorisant les puissances de 2 à partir de n − 1
ors, selon moi (je sait que j'ai tort), d sera toujours egal a 1...
facoriser un nombre pair par ses puissance de 2 sera toujours finit...
ou ais-je tort???

j'ai un petit pb de comprehension :'(

[zul]

Je ne suis pas sur de comprendre la notation.
Toutefois pour n = 21
n - 1 = 20 = 4 * 5 = 2^2 * 5;

donc ton d vaudra 5 ici.

[hansaplast]

Je ne suis pas sur de comprendre la notation.
Toutefois pour n = 21
n - 1 = 20 = 4 * 5 = 2^2 * 5;

donc ton d vaudra 5 ici.

merci :'(
j'ai honte

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