Génération de nombres premiers.

[Antikhippe]

Bonjour,

Dans le cadre de mes TPE sur la cryptographie, j'ai créé un programme en C++, dans lequel je voudrais insérer une partie consacrée à la génération de nombres premiers. Seulement, je n'ai aucune idée pour la réalisation de cette partie, notamment en ce qui concerne le cheminement mathématique. J'ai pensé à me sevir du crible d'Eratosthène mais ja ne sais pas comment l'exploiter.

Je ne vous demande pas de me faire le programme, bien sûr, mais j'aimerais savoir quelles sont les étapes mathématiques à programmer pour arriver à générer les X premiers nombres premiers.

En espérant que vous puissiez m'aider, je vous remercie d'avance.

Antikhippe.
-----

[invitedebe236f]

je t ecris ca en vb voire en francais
dim tab1(50000)

for i= 2 to 50000
tab1(i)=i
next i

for i= 2 to racine(50000)
if tab1(i)=i then
for j=i*i to 50000 step i *2
tab1(j)=0
next j
end if
next i

ce qui reste tab1(i)= i sont premier

[invitedebe236f]

step i*2 sauf pour 2 rhhaa la la

[martini_bird]

Salut,
je ne sais pas quelle méthode de cryptographie tu as implémentée (RSA?), mais je pense que tu auras besoin de grands nombres premiers, et dans ce cas le crible d'Erathostène risque d'être laborieux...

[A voir en vidéo sur Futura]

[leg]

je n'arrive pas a t'envoyer un extrait de l'algorithme P(30) program fait en C++
il s'agit de la factorisation de la série 1(30) ci dessous. les . = points représente les nombre premiers dans l'ordre croissant de cette série 1 modulo 30; il y a donc 6 cellules représentées par des . ou des couples de facteur premiers, la premiere cellule vaut 1 puis 31 , 61 . . . puis 7*13 = 91 ; 11*11 = 121; . = 151 voila pour la ligne 0
la ligne 1 sera: . = 181; . = 211 ; . = 241; . = 271; 7*43 =301 et . = 331
le principe est simple : 7 va compter 7 cellules en partant de sa base qui est la quatrième cellule il va arriver avec son conjoint = 43; il en sera de même pour 13 qui va compter 13 cellules son conjoint sera donc 7 + 30 = 37 .
deux critères pour savoir si le conjoint est premier: soit la base divise le conjoint alors il est composé donc élimine ou la base et son conjoint arrive dans une cellule qui est déja marqué par un facteur premier le conjoint est là aussi composé donc éliminé
lorsque le conjoint est premier et que c'est à lui de compter les cellules il compte jusqu'a la limite X defini par ex 10000. par exemple 37 ou 43 qui son des conjoints, lorsque c'est à leur tour de partir compter les cellules vide, ils marqueront de leur valeur ou d'un o toutes les 37 cellules ou 43 etc etc
les 8 bases qui sont obligatoirement premières sont : 7, 11, 13, 17, 19, 23, 29, et 31 qui remplace 1 ce dernier est un produit vide sans facteur!
seul est seulement les bases comptent leur nombres de cellule et attendent le tour suivant. dans ce tableau 7 compte 7 cellule puis ,13 puis 11 , a nouveau 7, 43 , 19,
17 , 23, a nouveau 11, 41 etc etc . ton programme a la fin compte les cellules vide qui sont les nombres premiers dans l'odre croissant congrue 1(30) pour cet exemple .
pour plus de détail fait moi le savoir ; amicalement leg
ps: cet algo factorise ou extrait les nombre premiers tu l'auras compris car pour factoriser chaque conjoint premier qui partira compter les cellules il indiquera sa valeur dans sa cellule au lieu de 0 par ex toute les 7 cellules il y aura un 7 ou toute les 43 cellules lorsque 43 par de sa cellule de base il y aura 43 etc . les nombres composés sont par conséquent absent car éliminé puisqu'ils arriveraient toujours dans une cellule marquée par des facteurs premiers!

0 . . . 7 - 13 11 - 11 .
1 . . . . 7 - 43 .
2 19 - 19 17 - 23 . 11 - 41 13 - 37 7 - 73
3
4 7 - 103 . 11 - 71 . 29 - 29 13 - 67
5 17 - 53 7 - 19 31 - 31 . . .
6 23 - 47 11 - 101 7 - 163 . . .
7 13 - 97 . . 7 - 193 . 17 - 83
8 11 - 131 . 19 - 79 . 7 - 223 43 - 37
9 . 13 - 127 41 - 41 29 - 59 . 7 - 11 - 23
10 . . . 31 - 61 17 - 113 .
11 7 - 283 . 13 - 157 19 - 109 11 - 191 .
12 . 7 - 313 . . . .
13 . . 7 11 - 13 - 17 23 - 107 53 - 47
14 29 - 89 7 - 373 19 - 139
15 73 - 37 11 - 251 7 - 13 - 31
16 67 - 43 71 - 41 17 - 173 7 - 433

[Antikhippe]

Waouuuh !!!

Merci beaucoup, les gars !!! Je ne pensais pas vous solliciter autant !
Je vais aller lire ça tranquillement puis je vous poserai éventuellement des questions.
Au fait, cricri, c'est pas toi qui a fait tes TPE sur la cryptographie car j'ai vu un site de crypto où il y avait un programme en VB avec une génération de nombres premiers ?

Encore merci !

[Antikhippe]

Salut,

je n'arrive pas a t'envoyer un extrait de l'algorithme P(30) program fait en C++

Est-ce que c'est toi qui l'as écrit ou alors tu l'as trouvé sur Internet ?

[leg]

Salut,


Est-ce que c'est toi qui l'as écrit ou alors tu l'as trouvé sur Internet ?

désolé mon ami il n'est pas connu, j'ai découvert cet algo, et j'ai fait faire le programme, par deux amis, afin d'analyser le comportement des nombre premiers dans l'ensemble P(30) pour trouver une relation et une contradiction a un nombre fini, des nombres premiers jumeaux, ce qui est presque confirmé! d'ou j'afirme qu'il y en a une infinité!
le programme a été fait en fonction des explications, que je vais t'envoyer les deux personne on fait deux programme différent: prime et nombre premier ;
prime : génère les nombre premiers et factorise les nombres composés en fonction du choix: prime.exe -p -s 1 10000 ; le programme extrait les nombres premiers de la série 1 jusqu'à 10000
prime.exe -f -s 1 10000 le programme factorise les nombre composé jusqu'à 10 000
A + je t'envoi un model si cela passe par le site sinon je t'adresse par ta méssagerie . leg

[leg]

S,1 S,7 S,11 S,13 S,17 S,19 S,23 S29
-- -- -- -- -- 7*7 -- --
-- -- -- -- 11*7 -- -- --
7*13 -- -- -- -- -- --
11*11 -- -- 7*19 -- -- 11*13 7*17
-- -- 7*23 -- -- 13*13 -- --
-- 11*17 -- -- -- -- 7*29 --
-- 31*7 17*13 -- -- -- -- 11*19
-- 13*19 -- 11*23 -- 7,37 -- --
-- -- -- -- 7,41 17*17 -- --
7,43 -- -- -- -- 11*29 17*19 13*23
-- -- 11*31 7,7,7 -- -- -- 7*47
19*19 7,53 13*29
17*23 31*13 11,37 7,59
7,61 23*19
11,41 7,67 11,43
13,37 17*29 7,71
7,73 11,47 31*17 23*23 13,41
19*29 7,79 13,43
7,83 11,53 31*19
13,47 7,89
13,7,7 11,59
23*29 11,61 7,97
17,41 19,37 7,101 31*23
7,103 17,43 11,67
7,109 13,59
11,71 7,113 13,61 17,47 11,73
19,43 17,7,7
29*29 11,11,7 23,37
13,67 7,127 19,47
53,17 11,83 7,131 13,71
7,7,19 23,41 13,73
31*31 7,139 11,89
13,11,7 17,59 19,53
13,79 17,61 7,149
7,151 11,97 29,37

11.101 7². 23
7 13. 89
11.107 7.13²
17.71 7.173
11.113 29. 43

j'ai du mal, a faire rentrer la série 29, cela n'est pas grave , les -- représent les cellules vide ce sont donc des nombres premiers. je vais t'envoyer par ton adresse ce même tableau avec les couleur par séries ce qui te permettra de distinguer les couple de basespar série et leurs position.
je viens de regarder ce que cela donne c'est la pagaille dans le tableau tu as déja l'explication ci dessous .je te renvois le tableau sur ton adresse et ensuite tu me recontacte.

Programmation, explication :

A/ Fixer la limite X = Nombre de cellules. Etablir le tableau : par exemple : 10000 cellules, soit la valeur 300000, une cellule vaut 30. Sauf la cellule 0 qui vaut la valeur de la série concernée, par exemple : 1, 7, 11……29.
Il y a 8 séries.
Les cellules sont représentées par des 0 donc des cellules vides, une cellule marquée par un 1 est une cellule composée, d’où cellule = 0 = Nombre Premier.
On peut limiter le nombre de cellule par tableaux ou faire un grand tableau divisé en sous-tableaux.

B/ Positionner les bases par rapport à la cellule zéro = 1, 7,……29. Par exemple pour la série 13 : la valeur de la cellule zéro = 13 puis on augmente de 30 à chaque cellule : soit : 43, 73,……..103 etc…. On positionne dans la cinquième cellule les bases 7 et 19 = F1 et F2, dans la 9ème cellules, les bases F3 et F4 = 11 et 23 ; dans la 14ème cellule, les bases F5 et F6 = 13 et 31 et dans la 17ème cellule, les bases F7 et F8 = 17 et 29.
« Valeur de la 17ème cellule = (16 x 30) + 13 = 17 x 29 = 493 »
Nous avons donc bien 4 cellules composées et 13 cellules premières. Pour générer les nombres premiers, il suffit de compter les 0 en partant de la cellule 0 = 13, puis + 30, soit 13, 43, 73, 103, c , 163, 193, 223, c,
Ce qui donne : 0 0 0 0 1 0 0 0 1
0 0 1 0 1 0 0 1 0 1 1 0 0 0 1 0 1 1
0 0 0 1 1 1 1 0 0
0 0 0 1 0 1
C/ Nous avons positionné les 8 bases ; maintenant on les fait partir, c’est-à-dire, elles vont compter leur nombre de cellules et se positionner avec leur conjoint = C + 30 et marquer la cellule en remplaçant le 0 par un 1…
Première base = 7 sans conjoint = (19 + 30) = 49 ; 7, compte 7 cellules, se positionne avec 49 dans la 12ème cellule et attend que les autres bases soient passées ; pareil pour la base 19 avec son conjoint = (7 + 30) = 37, va se positionner 19 cellules plus loin, c’est-à-dire 5 + 19 = 24ème et idem avec les 6 autres bases.

D/ Seul et seulement les bases divisent le conjoint avant que ce dernier ne parte compter les cellules jusqu’à la limite X fixée ; les bases se positionne toujours avec leur nouveau conjoint et attendent leur tour. Seul et seulement les conjoints si ils sont premiers comptent et marquent les cellules d’un 1 à chaque saut et ce, jusqu’à X fixé.

E/ Comment savoir si le conjoint C + 30 est premier :
1/ Lorsque la base arrive dans une cellule marquée par un 0.
Si la base arrive avec son conjoint dans une cellule marquée par 1, alors : ce conjoint est composé, donc effacé, il ne comptera pas de cellule. Seule les bases ou les conjoints premiers comptent et marquent les cellules d’un 1
2/ Si la base divise le conjoint C + 30, alors là aussi, c’est qu’il est composé donc effacé : Exemple : (49/7 = 7 ; 37/19 = 1.94). Lorsque 7 va se positionner dans la 12ème cellule avec C + 30 = 19 + 30 = 49, la 12ème cellule étant marquée par un 0 lorsque les 7 autres bases sont passées, elles n’ont pas marquées d’un 1 la 12ème cellule, on pourrait donc penser que 49 est premier : Or, 7 divise 49, ce qui est le deuxième contrôle donc 49 est effacé, la base 7 partira recompter 7 cellules, ira se positionner avec son nouveau conjoint C + 30 = 49 + 30 = 79, dans la 19ème cellule marquée par un 0 ; 7 ne divise pas 79, lorsque les bases seront passées et que cela sera le tour de 79 de partir, 79 marquera d’un 1 toutes les 79 cellules jusqu’à la limite X fixée sans s’arrêter.

F/ Lorsque les bases ont atteints la limite X, le programme compte toutes les cellules marquées par un 0, on aura donc le nombre de nombre premier jusqu’à X et les nombres premiers 13 + 30 + 30 + 30 + 30….
« Ne sont retenues que les valeurs des cellules marquées par un 0 bien entendu »
Factorisation des cellules composées, c’est exactement le même programme à la différence que là, au lieu de marquer les cellules par un 1, on marque la valeur de la base ou du conjoint premier C + 30 dans les cellules, par exemple : 5ème cellule = 7, 19 ; 9ème cellule = 13.23, 14ème cellule = 13.31 ; 17ème cellule = 17.29, 19ème cellule = 7 uniquement, 49 est composé = 7 x 7, 24ème cellule, 19.37 ; etc…etc…

Les facteurs composés ayant été effacés, il n’y aura que la décomposition des cellules composées en facteurs premiers. On l’aura compris, un e cellule avec un seul facteur, c’est un facteur premier à la puissance N, ce qui nous intéresse c’est les facteurs distincts d’un nombre composé. Exemple 12ème cellule, il n’y aura que 7 dans la cellule et non pas trois 7 comme on peut le voir dans le tableau ci-joint, cela a été fait manuellement pour comprendre.

G/ Il en sera de même pour les 7 autres séries ci-joint en factorisation.

(Les fichiers sources du programme prime ou, nombre premier sont écris en C++.
Le programme nombre premier énumère les nombres premiers jusqu’à 450000000000, par série , dans l’ordre croissant, en 1 heure avec un PC ayant 2 Gigas de ram ; car Windows n’alloue que 2094 Mo par instance de programme.
Amicalement leg.

[invitea8961440]

Au lieu du crible d'Erastosthene,pense à l'algorithme KAS (Kayal,Agrawal,Saxena),cela te sera d'un précieux intéret.

[Antikhippe]

Au lieu du crible d'Erastosthene,pense à l'algorithme KAS (Kayal,Agrawal,Saxena),cela te sera d'un précieux intéret.

Tu as sans doute raison, et j'y avais déjà pensé, mais avant que je maîtrise le sujet...
http://www.cse.iitk.ac.in/news/primality.pdf