calcule de nombre premier

Le
Talus
Bonjour a tous je cherche une fonction ou un algo pour le calcule et la
verification de nombre, pour savoir si un nombre est premier ou non, les
nombre etant des nombre tres grand il faudrait que la fonction soit eficace
pour realisée les calcul rapidement, mais apres une longue recherche sur le
net je n'ai trouvée que des methode et non des algo ou fonction expliquée

Merci a vous d'avance
Vidéos High-Tech et Jeu Vidéo
Téléchargements
Vos réponses Page 1 / 2
Gagnez chaque mois un abonnement Premium avec GNT : Inscrivez-vous !
Trier par : date / pertinence
Antoine
Le #16736491
Talus wrote:
Bonjour a tous je cherche une fonction ou un algo pour le calcule et la
verification de nombre, pour savoir si un nombre est premier ou non, les
nombre etant des nombre tres grand il faudrait que la fonction soit eficace
pour realisée les calcul rapidement, mais apres une longue recherche sur le
net je n'ai trouvée que des methode et non des algo ou fonction expliquée

Merci a vous d'avance





Une méthode classique :

#include #include #include <iostream>
#include using namespace std;

BOOL IsPrimeNumber(int);

void main()
{
int n;
cout << "Entrez un nombre : ";
cin >> n;
if (IsPrimeNumber(n))
cout << "Premier" << endl;
else
cout << "Non Premier" << endl;
getch();
}

BOOL IsPrimeNumber(int n)
{
int i;
bool IsPrime=true;
for (i=2; i<=sqrt(static_cast<double>(n)) && IsPrime; i++)
if (n%i==0)
IsPrimeúlse;

return IsPrime;
}
Sylvain SF
Le #16737561
Antoine wrote on 06/09/2008 18:01:

je cherche une fonction pour la verification de nombre premier



BOOL IsPrimeNumber(int n){
bool IsPrime=true;
for (int i=2; i<=sqrt(static_cast<double>(n)) && IsPrime; i++)
if (n%i==0)
IsPrimeúlse;
return IsPrime;
}



superbe méthode ! bon, c'est la plus lente possible (calcul de
constante dans la boucle, couteux modulo) et ça ne marche qu'avec
des nombres inférieurs à 31 bits, mais le principe est un peu là.

les 200000 premiers nombres premiers (de 2 à 2750159) se détectent
généralement par une table constante, ensuite viennent les algos
PrimeSieve, ceux de Jacobi, Lucas, Rabin-Miller, ...

il est plus simple d'utiliser une librairie existante que de réinventer
l'eau tiède en la matière.

Sylvain.
Jean Bon (de Parme)
Le #16739781
On Sat, 06 Sep 2008 19:33:04 +0200, Sylvain SF

Antoine wrote on 06/09/2008 18:01:

je cherche une fonction pour la verification de nombre premier



BOOL IsPrimeNumber(int n){
bool IsPrime=true;
for (int i=2; i<=sqrt(static_cast<double>(n)) && IsPrime; i++)
if (n%i==0)
IsPrimeúlse;
return IsPrime;
}



superbe méthode ! bon, c'est la plus lente possible (calcul de
constante dans la boucle, couteux modulo) et ça ne marche qu'avec
des nombres inférieurs à 31 bits, mais le principe est un peu là.

les 200000 premiers nombres premiers (de 2 à 2750159) se détectent
généralement par une table constante, ensuite viennent les algos
PrimeSieve, ceux de Jacobi, Lucas, Rabin-Miller, ...

il est plus simple d'utiliser une librairie existante que de réinventer
l'eau tiède en la matière.

Sylvain.



C'est pas plus simple de mettre une bonne fois pour toute ces nombre
premier dans une base a telecharger ?

C'est quand meme autremement plus rapide (a defaut peut etre d'etre
plus volumineux)
Talus
Le #16740091
en faite j'utiliserai cette fonction dans un algo de cryptage, donc le
calcul, et la verification des nombres devra etre assez rapide etant donnée
la grandeur de ceux ci par exemple :

7468778241636094714559118172311160479355776440953393291497617236694813600756621941132062107376402703

qui est un nombre premier bien sur.
Sylvain SF
Le #16740221
Talus wrote on 07/09/2008 01:05:
en faite j'utiliserai cette fonction dans un algo de cryptage



de chiffrement. lequel ?

donc le calcul



la génération ? parce que "calculer" un nombre premier ?...

et la verification des nombres devra etre assez rapide



et plus important encore exacte !

Sylvain.
Solanar
Le #16740321
Maître "Talus" nous raconte
en faite j'utiliserai cette fonction dans un algo de cryptage, donc le
calcul, et la verification des nombres devra etre assez rapide etant
donnée la grandeur de ceux ci par exemple :

7468778241636094714559118172311160479355776440953393291497617236694813600756621941132062107376402703

qui est un nombre premier bien sur.



Il est divisible par 173

--
Solanar
"Etre libre, c'est n'avoir rien à perdre"
Sylvain SF
Le #16740351
Solanar wrote on 07/09/2008 03:31:

7468778241636094714559118172311160479355776440953393291497617236694813600756621941132062107376402703

qui est un nombre premier bien sur.



Il est divisible par 173



s'il fallait le lire en base 16, mais il est écrit en base 10.
(0xda8a3e75fa343eeb51236bab6ac514c174d2d7c8b1ddbc43053df30f73518454e4908ba04ed3f29c10f
est bien premier).

Sylvain.
Sylvain SF
Le #16740341
Jean Bon (de Parme) wrote on 07/09/2008 00:01:

C'est pas plus simple de mettre une bonne fois pour toute ces nombre
premier dans une base a telecharger ?



si vous fixez une limite faible à leurs taille, c'est possible.
si vous montez en taille 4096 bits ou plus il y a une "infinité"
de nombres premiers, par définition vous ne les mettrez jamais
tous en base.

C'est quand meme autremement plus rapide



les tests de primalité ne sont réalisés qu'une seule fois, à la
génération de la clé basée sur des nombres premiers, le temps
n'est pas un trop gros problème (hormi système embarqué comme
une carte à puce); certains algo peuvent utilisés des aléa.
premiers pour chaque nouveau calcul mais ils utilisent des
petits nombres (1024-1536 bits) qui sont vite vérifiés.

Sylvain.
Talus
Le #16741501
"Sylvain SF" 48c313c4$0$871$

Talus wrote on 07/09/2008 01:05:
en faite j'utiliserai cette fonction dans un algo de cryptage



de chiffrement. lequel ?

donc le calcul



la génération ? parce que "calculer" un nombre premier ?...

et la verification des nombres devra etre assez rapide



et plus important encore exacte !

Sylvain.





l'algo est un dérivée du Diffie-Hellman, que j'ai mit au point, pour cryptée
les clefs utilisée lors du cryptage de donnée avec un autre algo (qui est
aussi de mon invention, lui est un dérivée de LUCIFER, enfin le principe
s'en raproche).

Un peu a la manière de PGP qui crypte les données en DES, ou en IDEA puis
les clef utilisée sont cryptée en RSA ce qui rend le système assez
sécurisée.



Dans mon cas il n'y aura qu'un seul nombre premier utilisée dans la clef
publique pour générée un delta, permettant de générée lui par la personne
désirant cryptée un message ,pour celui ayant cette clef publique, une clef
de cryptage, qui dans certaine condition peut être qualifiée de jetable.



si vous avez des question sur mes algo qui pourrai vous aidez, je vous les
transmettrai
Serge Paccalin
Le #16743071
Le dimanche 7 septembre 2008 à 00:01:44, Jean Bon (de Parme) a écrit
dans fr.comp.os.ms-windows.programmation :

C'est pas plus simple de mettre une bonne fois pour toute ces nombre
premier dans une base a telecharger ?



Non. Il y a tellement de nombres premiers que c'est totalement
infaisable et irréaliste au-delà de quelques petites dizaines de bits,
et il faudrait monter à plusieurs milliers.

C'est bien pire que les grains de blé du l'inventeur du jeu d'échecs.

--
___________
_/ _ _`_`_`_) Serge PACCALIN -- sp ad mailclub.net
_L_) Il faut donc que les hommes commencent
-'(__) par n'être pas fanatiques pour mériter
_/___(_) la tolérance. -- Voltaire, 1763
Publicité
Poster une réponse
Anonyme