>> Sécurité de l'état / Nombres premiers

[invite3d7be5ae]

Pour Fermat on utilise le "petit" théorème de Fermat :
Si p est premier alors p divise a^p-a pout tout a. On peut donc ce servir de ce théorème pour avoir un test de primalité.
Attention : 2^561-2 divise 561.
Cherchez un peu sur Google avec "nombres de Carmichael"

Solovay-Strassen (a/p) (Symbole de Jacobi)=a^((p-1)/2) mod p.
Pour k test, on est sûr à 1-1/2^k (si à chaque fois c'est égal) que n est premier, sinon on est sûr qu'il est composé.

Erathostène : vous devrez savoir.

Rabin-Miller:C'est dérivé du test de Fermat.
Pour k test, on est sûr à 1-1/4^k (sauf s'il est composé).

ECPP : courbes elliptiques un programme de François Morain est disponible.

Eratosthène et ECPP sont des algorithme sûr (mathématiquement).

Alors la factorisation est difficile (qui peut le prouver?) n'est-ce pas?.

561=3*11*17
-----

[invitefc3f0b55]

Bonjour
c'est interessant tous ca , ce qui j'ai à ajouté c'est que plusieur cryptosysème a clef publique comme RSA utilise pour chiffrerer une information le produit de deux nombre premiers de grand taille, et pour le dicchiffrer il faut soit avoir la bonne clefs ( privé) soit pouvoir factorizer le produit et trouver les deux nombre premier du depart, d'apres mes connaissances une clef de 128 bit et largement suffisante ( ce qui veut dire produit (de deux nombre premier) de 128
est difficille a factoriser ) donc je croit que la publication des nombres premiers de grand tailles n est pas interdite sauf si' il, mais par contre des algorithmes de factorizations la on eut poser la question.

[invite3d7be5ae]

On a reussi a craquer des clefs de 256 bit (pour les nombres premiert et donc 512 bits pour le produit).

128 bits~=40 chiffres

[invite3d7be5ae]

Alors c'est quoi cette méthode?

[SPH]

Ma methode n'est pas l'une de celle que tu as exposé. C'est simple, je trouve les nombres premiers sans aucun calcul

[erik]

C'est simple, je trouve les nombres premiers sans aucun calcul

Pour faire cela, à part consulter une liste de nombres premiers déja calculés, je ne vois pas très bien ce que tu veux dire.
Pourrais tu satisfaire notre curiosité, et détailler ce que tu veux dire par là ?

[invite3d7be5ae]

Tu fais même pas des additions?
Ca ne ressemble pas à ça (turbo pascal) :

const max=1 000 000 000;(* en fait il n'y a pas de " " *)
max_prem=trunc(max/ln(max)*1.04423);
type tableau=array[1..max_prem]of longint;

procedure erathos(var premier:tableau);

var crible:set of longint;
nombre,k,i:longint;
begin
crible:=[2..max];
nombre:=2;k:=1;
repeat
while not (nombre in crible) do inc(nombre);
premier[k]:=nombre;
inc(k);
i:=nombre;
while i<=max do begin
crible:=crible-[i];
i:=i+nombre;
end;
until crible=[];
end;

Tu l'as peut être programmer en assembleur pour qu'il soit plus rapide.
Mais cet algo fait des calculs : il ajoute 1 (inc).

Détaille s'il te plaît ton algo.

end;

[SPH]

Mon algo qui pour l'instant est secret ne manipule aucun nombre premier. En fait, il se fiche bien de savoir ce qui est premier ou non. La, je suis en train de transformer certaines parties en ASM et je suis aussi limité a ne trouver que les NP entre 0 et 2 milliards car j'ai un overflow naturel. Mais c'est facilement contournable. Je bosse donc dessus.
PS: ton code trouve t'il IMMEDIATEMENT les 100 premiers NP (par exemple) ou bien doit il calculer assez "longtemps" pour preparer le terrain afin de trouver les grands NP ? (apparement, tu fais un calcul pour voir si chaque nombre est un NP. Moi pas)
car moi, avant ca, je devais preparer le terrain du nombre "3" (tres longue attente) par exemple et plus le temps passait, plus mon programme allait vite pour devoiler les autres NP. Maintenant, fini la manipulation de "3" et autres "5", "7", etc. Tous les NP sont détecté aussi rapidement qu'un :
for i=0 to 2000000000
print NP(i)
next
(cette image basic illustre la rapidité, mais pas la simplicité de mon code...)
ps2: je vais voir si je peux participer au concours du premier nombre de mersenne a 10 millions de chiffres. Voila pourquoi, pour l'instant, je ne dis rien.

[inviteab2b41c6]

Vos trucs d'algo ne seraient ils pas mieux logés dans la section info?

[erik]

Tous les NP sont détecté

Tu comptes trouver tout les nombres premiers entre 2 et 10^10 000 000 !!!
Je pense que tu n'as pas bien lu les précedents messages.
Petit exercice : imagine qu'il te faille (au hasard) 10^-43 seconde par nombre, au bout de combien de temps arrives tu à 10^10 000 000 ?

Ou alors j'ai mal compris et tu es en train d'écrire un programme qui determine si un nombre p est premier ou non (ce qui est different d'un programme qui sort la liste des nombres premiers jusqu'a une certaine valeur)

[invitedebe236f]

sans cacul il utile le crible d Erathostène

je vois que ca

[SPH]

sans cacul il utile le crible d Erathostène

je vois que ca

Ca alors, je viens de regarder de qu'est ce crible et en effet, je bosse la dessus (sans savoir si ca existait). Mais j'ai ajouter une variante qui accelere GRANDEMENT le systeme !!!!!!!!!!!!! (et je dis bien "GRANDEMENT")

[invite3d7be5ae]

Il enlève une partie de la mémoire nécessaire?

Dis nous ton algo. Tu n'arriveras jamais aux 10^(10^6). Pour cela il te faudra beaucoup de mémoire. Tu en es où exactement?

[invite3d7be5ae]

Alors, SPH tu nous donnes ton algo?
J'ai envie de le programmer pour voir sa vitesse.

[invite76e2b617]

Tiens, est-il possible d'adapter le crible d'Eratosthène pour qu'il ne porte que sur les suites 6n+1 et 6n-1, cela éliminerait pas mal de cas. A part 2 et 3, tous les premiers sont dans ces 2 suites, non ?

[SPH]

Non, je ne donnerais pas mon algo. Il est tres rapide mais pose un certain probleme de place memoire. Alors, je l'adapte a nouveau pour directement voir ce qui se passe a partir de 2^n (soit un nombre de 10 million de chiffres).
De plus, je converti la majeure partie de mon prog en ASM sinon, ce n'est meme pas la peine.
Ha ba tiens, si tu veux savoir où j'en suis, voila un programme en cours de transformation en ASM et qui calcul 2^n et indique le nombre de chiffre que ca prend (le chiffre etant reellement calculé et stocké en bank) :
PROGRAMME AVEC 20% D'ASM

[invite97a92052]

[mode HS, mais ça peut servir]

Si tu veux aller plus vite, utilise une librairie de grands nombres... !

J'ai refait ton programme avec GMP, et avec mon vieux 450 MHz, j'en suis déjà à 2^536870912 en à peu près 8 secondes (alors que pendant le même temps, j'ne suis à 2^32768 avec ton programme)

#include <stdio.h>
#include <gmp.h>
#include <math.h>

int main(void) {
	
	mpz_t
		entier[31];
	unsigned long
		exposant=1,
		chiffres;

	for(unsigned i=0; i<31; ++i) {
		mpz_init(entier[i]);
		mpz_ui_pow_ui(entier[i], 2UL, exposant);
		chiffres = (unsigned long)(floor(((double)exposant) * log(2.0) / log(10.0))) + 1UL;
		printf("-----\n2^%lu\nChiffres :%lu\n", exposant, chiffres);

		exposant <<= 1;
	}

	for(unsigned i=0; i<31; ++i)
		mpz_clear(entier[i]);

	getchar();
	return 0;
}

(bon, il faut attendre très longtemps pour libérer la mémoire dans de bonnes conditions, mais c'est juste pour donner l'idée du truc)

[invite3d7be5ae]

...j'en suis déjà à 2^536870912 en à peu près 8 secondes

2^536 870 912, ça fait plus de 100 000 000 de chiffres.

g_h tu vas être célèbre si tu connais ce nombre premier.

Comment tu fait pour traduire 2^asm.exe en C++?

SPH, quand je voulais dire où tu en ais, je voulais savoir où tu en étais dans tes nombres premiers.

[invite97a92052]

2^536 870 912, ça fait plus de 100 000 000 de chiffres.

Oui, 161 614 249 pour être précis... d'ailleurs, au bout de 25 secondes environ, j'obtiens 2^1073741824, soit 2²³⁰qui fait 323 228 497 chiffres en base 10 (je m'arrête à 30 dans le programme car 2²³¹ fait exploser ma mémoire)

g_h tu vas être célèbre si tu connais ce nombre premier.

Ce nombre là est loin d'être premier avec son milliard de diviseurs !

Comment tu fait pour traduire 2^asm.exe en C++?

Heu, j'ai juste refait le programme (en C, pas en C++ ) à la main d'après les indications de SPH :

voila un programme en cours de transformation en ASM et qui calcul 2^n et indique le nombre de chiffre que ca prend

Il n'est pas possible de traduire directement un exécutable non interprété vers des langages comme C ou C++, tu peux juste le désassembler, et si tu maîtrise bien l'assembleur, tu peux arriver à le comprendre et à le réécrire, mais il faut vraiment le vouloir (et avoir énormément de pratique).

[invite3d7be5ae]

Ton programme calcule donc 2^(2^x). Je ne vois pas le rapport avec les nombres premiers...

Alors que celui de SPH, calcule un nombre premier et affiche sa taille si elle est assez grande.

Calculer des puissances (2^(2^x)) est bien entendu plus rapide que savoir si un nombre est premier.

[erik]

Calculer des puissances (2^(2^x)) est bien entendu plus rapide que savoir si un nombre est premier.

Et je rajouterai qu'il est totalement impossible de determiner si un nombre de la taille de 2^2^30 (c'est à dire avec 100 000 000 chiffres) est premier ou non à l'aide d'un algo de type crible d'Erathostene (même amélioré). Tout simplement pour des problèmes d'espace mémoire.

[invite76e2b617]

Le programme qu'a donner SPH ne donne pas de premiers, il calcul 2^n.

[invite97a92052]

Ton programme calcule donc 2^(2^x). Je ne vois pas le rapport avec les nombres premiers...

Alors que celui de SPH, calcule un nombre premier et affiche sa taille si elle est assez grande.

Calculer des puissances (2^(2^x)) est bien entendu plus rapide que savoir si un nombre est premier.

T'as executé le programme de SPH ? Tu remarqueras qu'il fait exactement la même chose que le mien, la seule différence étant que lui y va tout seul en assembleur tandis que j'utilise GMP que je lui conseillais car c'est autrement plus rapide.

Et je sais que calculer 2^2^X est plus facile que de savoir si un nombre est premier, merci !


En tous cas j'avoue être perdu, je ne vois pas ou SPH s'engouffre avec ses 2^x...

[SPH]

Oui, mon code actuel fait bien 2^x. Mais je l'ai amélioré. Par contre, G_h, tu dis que tu es a 2^536870912 en à peu près 8 secondes ??? TU ES SUR ?????????
Perso, j'en doute beaucoup !!!! Car, soit tu le stock en banque, soit tu as un overflow. Alors, je ne vois pas comment tu fais. Et meme si tu y arrive, je ne pense pas qu'on puisse y arriver en 8 secondes...

Pour les autres : A la base, je voulais savoir si un nombre est premier. Mais, pour savoir si un nombre de mersenne est premier, je prefere deja ecrire une serie de nombres de 10 millions de chiffres de format (2^x)-1 puis cribler avec mon algo. Mais maintenant, si G_H atteint reellement la vitesse qu'il dit, alors je suis grillé et ce n'est pas la peine que je continue. Par contre, si j'adapte mon code a la technique de G_H pour atteindre sa vitesse, alors, ca vaux vraiment le coup.

PS : Mon code est a 50% ASM environ et il va bien plus vite que le premier. Mais je ne sais si j'atteindrais la vitesse de G_H avec un code a 100% ASM.

[invite3d7be5ae]

Pourquoi vous vous cassez la tête à caluler des puissances de 2?
Maple me donne en 1 seconde 2^(2^20).

Java, en 1 seconde me donne 2^(2^18).
Alors que ton algo à 50%asm me donne en 1 seconde 2^(2^14).
SPH, tu travaille pour rien.

10^160 000 000~=2^500 000 000 (Caluler de tête)
Je ne savais pas que les ordis à 450MHz avais 512Mo de Ram. Et encore, il devrait plutôt avoir 1Go de Ram. Bizarre ton affaire g_h.

[SPH]

Pourquoi vous vous cassez la tête à caluler des puissances de 2?

Parce que pour un criblage des nombres premiers, je prefere finalement cribler un nombre de format (2^n)-1 (nombre de mersenne).

Maple me donne en 1 seconde 2^(2^20).
Java, en 1 seconde me donne 2^(2^18).
Alors que ton algo à 50%asm me donne en 1 seconde 2^(2^14).
SPH, tu travaille pour rien.

Quand je regarde mon code, il manque une partie importante en ASM. Quand je l'aurais fait, je pense etre aussi rapide que Maple.

10^160 000 000~=2^500 000 000 (Caluler de tête)
Je ne savais pas que les ordis à 450MHz avais 512Mo de Ram. Et encore, il devrait plutôt avoir 1Go de Ram. Bizarre ton affaire g_h.

Tout est possible. Il suffit de rajouter lde la memoire.

[SPH]

A propos, le temps d'attente de vos routine est il exponentiel ? (comme mon code)

[invite97a92052]

Pourquoi vous vous cassez la tête à caluler des puissances de 2?
Maple me donne en 1 seconde 2^(2^20).

Java, en 1 seconde me donne 2^(2^18).
Alors que ton algo à 50%asm me donne en 1 seconde 2^(2^14).
SPH, tu travaille pour rien.

Je suis d'accord ! Etre aussi rapide que maple ou GMP ça serait un exploit je pense.

10^160 000 000~=2^500 000 000 (Caluler de tête)
Je ne savais pas que les ordis à 450MHz avais 512Mo de Ram. Et encore, il devrait plutôt avoir 1Go de Ram. Bizarre ton affaire g_h.

Hein ???!?
Si tu refais ton calcul correctement, tu verras qu'il suffit d'un peu moins de 60Mo pour stocker 2^500000000
(j'ai 128mo de ram d'ailleurs)


[je propose que cette discussion soit déplacée ailleurs]

[SPH]

[je propose que cette discussion soit déplacée ailleurs]

Non, cette discution est mathematique, non ?

[invitedebe236f]

2^536870912 en environ 7 min bien sur avec tous les chiffres
j ai utiliser la fft au lieu de la hartley (avec je devrai aller plus vite)

tu met combien de temps ?