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
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.
Mais ça dépend jusqu'où l'on veut aller. Jusqu'à quelques trilliards ou plus, avec une base Oracle ou autre, on retrouve immédiatement par l'index si le nombre est premier.
Serge Paccalin wrote:
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.
Mais ça dépend jusqu'où l'on veut aller.
Jusqu'à quelques trilliards ou plus, avec une base Oracle ou autre, on
retrouve immédiatement par l'index si le nombre est premier.
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.
Mais ça dépend jusqu'où l'on veut aller. Jusqu'à quelques trilliards ou plus, avec une base Oracle ou autre, on retrouve immédiatement par l'index si le nombre est premier.
Serge Paccalin
Le dimanche 7 septembre 2008 à 12:46:13, Antys 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.
Mais ça dépend jusqu'où l'on veut aller.
Je l'ai dit : plusieurs milliers de bits (je parle ici de la longueur des nombres premiers en question).
Jusqu'à quelques trilliards ou plus, avec une base Oracle ou autre, on retrouve immédiatement par l'index si le nombre est premier.
Tous les nombres premiers jusqu'à 1024 bits de longueur, par exemple, cela fait combien de trilliards, d'après toi ?
-- ___________ _/ _ _`_`_`_) 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
Le dimanche 7 septembre 2008 à 12:46:13, Antys 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.
Mais ça dépend jusqu'où l'on veut aller.
Je l'ai dit : plusieurs milliers de bits (je parle ici de la longueur
des nombres premiers en question).
Jusqu'à quelques trilliards ou plus, avec une base Oracle ou autre, on
retrouve immédiatement par l'index si le nombre est premier.
Tous les nombres premiers jusqu'à 1024 bits de longueur, par exemple,
cela fait combien de trilliards, d'après toi ?
--
___________
_/ _ _`_`_`_) 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
Le dimanche 7 septembre 2008 à 12:46:13, Antys 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.
Mais ça dépend jusqu'où l'on veut aller.
Je l'ai dit : plusieurs milliers de bits (je parle ici de la longueur des nombres premiers en question).
Jusqu'à quelques trilliards ou plus, avec une base Oracle ou autre, on retrouve immédiatement par l'index si le nombre est premier.
Tous les nombres premiers jusqu'à 1024 bits de longueur, par exemple, cela fait combien de trilliards, d'après toi ?
-- ___________ _/ _ _`_`_`_) 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
Solanar
Maître "Jean Bon (de Parme)" nous raconte
On Sat, 06 Sep 2008 19:33:04 +0200, Sylvain SF wrote:
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)
Il existe un nombre infini de nombres premiers car on peut toujours a partir d'un nombre premier en déduire l'existence d'un plus grand que lui Si on a ppelle GNP ce nombre défini comme le plus grand des nombres premiers on peut calculer factorielle GNB+1 FGNB
Ce FGNB ne sera evidement divisible par aucun des nombre plus petits que GNP (reste 1 a toutes les divisions) Donc soit FGNB est premier soit FGNB est divisible par un nombre premier plus grand que GNP CQFD
-- Solanar "Etre libre, c'est n'avoir rien à perdre"
Maître "Jean Bon (de Parme)" nous raconte
On Sat, 06 Sep 2008 19:33:04 +0200, Sylvain SF
<sylvain@boiteaspam.info> wrote:
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)
Il existe un nombre infini de nombres premiers car on peut toujours a partir
d'un nombre premier en déduire l'existence d'un plus grand que lui
Si on a ppelle GNP ce nombre défini comme le plus grand des nombres premiers
on peut calculer factorielle GNB+1 FGNB
Ce FGNB ne sera evidement divisible par aucun des nombre plus petits que GNP
(reste 1 a toutes les divisions)
Donc soit FGNB est premier soit FGNB est divisible par un nombre premier
plus grand que GNP
CQFD
--
Solanar
"Etre libre, c'est n'avoir rien à perdre"
On Sat, 06 Sep 2008 19:33:04 +0200, Sylvain SF wrote:
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)
Il existe un nombre infini de nombres premiers car on peut toujours a partir d'un nombre premier en déduire l'existence d'un plus grand que lui Si on a ppelle GNP ce nombre défini comme le plus grand des nombres premiers on peut calculer factorielle GNB+1 FGNB
Ce FGNB ne sera evidement divisible par aucun des nombre plus petits que GNP (reste 1 a toutes les divisions) Donc soit FGNB est premier soit FGNB est divisible par un nombre premier plus grand que GNP CQFD
-- Solanar "Etre libre, c'est n'avoir rien à perdre"
Sylvain SF
Talus wrote on 07/09/2008 10:46:
si vous avez des question sur mes algo qui pourrai vous aidez, je vous les transmettrai
certainement ! soit utiliser "encrypt" et "wrap" bien que sur une branche fr. de usenet, soit ne pas utiliser le néologisme barbare crypter qui ne veut rien dire.
par ailleurs, lever un doute: vous dites avoir mis au point une variante de DH mais chercher une fonction expliquant (pas à pas?) la vérification de primalité, les compétences pour la première condition n'incluerait pas la seconde ?
Sylvain.
Talus wrote on 07/09/2008 10:46:
si vous avez des question sur mes algo qui pourrai vous aidez, je vous les
transmettrai
certainement ! soit utiliser "encrypt" et "wrap" bien que sur une
branche fr. de usenet, soit ne pas utiliser le néologisme barbare
crypter qui ne veut rien dire.
par ailleurs, lever un doute: vous dites avoir mis au point une
variante de DH mais chercher une fonction expliquant (pas à pas?)
la vérification de primalité, les compétences pour la première
condition n'incluerait pas la seconde ?
si vous avez des question sur mes algo qui pourrai vous aidez, je vous les transmettrai
certainement ! soit utiliser "encrypt" et "wrap" bien que sur une branche fr. de usenet, soit ne pas utiliser le néologisme barbare crypter qui ne veut rien dire.
par ailleurs, lever un doute: vous dites avoir mis au point une variante de DH mais chercher une fonction expliquant (pas à pas?) la vérification de primalité, les compétences pour la première condition n'incluerait pas la seconde ?
Sylvain.
Antys
Sylvain SF wrote:
Talus wrote on 07/09/2008 10:46:
si vous avez des question sur mes algo qui pourrai vous aidez, je vous les transmettrai
certainement ! soit utiliser "encrypt" et "wrap" bien que sur une branche fr. de usenet, soit ne pas utiliser le néologisme barbare crypter qui ne veut rien dire.
Si, c'est d'usage courant: http://www.linternaute.com/dictionnaire/fr/definition/crypter/ (pour les chaînes TV notamment)
Sylvain SF wrote:
Talus wrote on 07/09/2008 10:46:
si vous avez des question sur mes algo qui pourrai vous aidez, je vous
les transmettrai
certainement ! soit utiliser "encrypt" et "wrap" bien que sur une
branche fr. de usenet, soit ne pas utiliser le néologisme barbare
crypter qui ne veut rien dire.
Si, c'est d'usage courant:
http://www.linternaute.com/dictionnaire/fr/definition/crypter/
(pour les chaînes TV notamment)
si vous avez des question sur mes algo qui pourrai vous aidez, je vous les transmettrai
certainement ! soit utiliser "encrypt" et "wrap" bien que sur une branche fr. de usenet, soit ne pas utiliser le néologisme barbare crypter qui ne veut rien dire.
Si, c'est d'usage courant: http://www.linternaute.com/dictionnaire/fr/definition/crypter/ (pour les chaînes TV notamment)
Talus
"Sylvain SF" a écrit dans le message de news: 48c3f5be$0$908$
Talus wrote on 07/09/2008 10:46:
si vous avez des question sur mes algo qui pourrai vous aidez, je vous les transmettrai
certainement ! soit utiliser "encrypt" et "wrap" bien que sur une branche fr. de usenet, soit ne pas utiliser le néologisme barbare crypter qui ne veut rien dire.
par ailleurs, lever un doute: vous dites avoir mis au point une variante de DH mais chercher une fonction expliquant (pas à pas?) la vérification de primalité, les compétences pour la première condition n'incluerait pas la seconde ?
Sylvain.
DH est juste une methode permetant de definir une clef sans que celle ci soit difusée.
voila le principe de DH, enfin le principe derivée que j'ai etabli avec DH
Choisir un nombre premier Pa Choisir un nombre Ya avec Ya<Pa Choisir un troisieme nombre totalement quelconque qui sera la clef privée, ici Clef_P_a
la clef publique et composé de Ya, Pa et d'un troisieme membre qui est calculée en fonction de Ya, Pa et Clef_P_a j'apelerai ce troisieme membre Delta_a
Delta_a = Ya^Clef_P_a (mod Pa) Ici le simbole ^ , coresspont au simbole exposant
l'utilisateur A, peut difusée sa clef publique : Ya, Pa et Delta_a
Un utilisateur B veut envoyée des donnée a A mais pour cela il utilise un Algo peu importe lequelle, mais il doit definir un clef que A pourra retrouvée grace a sa clef privée
pour cela B recupere la clef publique de A et grace a sa clef privée Clef_P_b il calcule la clef de cryptage ici K
K = Delta_A^Clef_P_b (mod Pa)
il crypte sont fichier a l'aide de la clef K.
puis il doit fournir à A une information qui lui permetrai de retrouvée la clef pour cela B vas calculer Delta_dec :
Delta_dec = Ya^Clef_P_b (modPa)
il envois donc à A les donnée cryptée et Delta_dec
A recois les donnée de B et le Delta_dec A calcule alors la clef de decryptage :
K = Delta_dec^Clef_P_a (mod Pa)
puis decrypte les données
Bien sur cela ne fonction que si P est un nombre premier, et plus P est grand plus la clef est dur a etre retrouvée pour toute personne tentant de decryptée les données
"Sylvain SF" <sylvain@boiteaspam.info> a écrit dans le message de news:
48c3f5be$0$908$ba4acef3@news.orange.fr...
Talus wrote on 07/09/2008 10:46:
si vous avez des question sur mes algo qui pourrai vous aidez, je vous
les transmettrai
certainement ! soit utiliser "encrypt" et "wrap" bien que sur une
branche fr. de usenet, soit ne pas utiliser le néologisme barbare
crypter qui ne veut rien dire.
par ailleurs, lever un doute: vous dites avoir mis au point une
variante de DH mais chercher une fonction expliquant (pas à pas?)
la vérification de primalité, les compétences pour la première
condition n'incluerait pas la seconde ?
Sylvain.
DH est juste une methode permetant de definir une clef sans que celle ci
soit difusée.
voila le principe de DH, enfin le principe derivée que j'ai etabli avec DH
Choisir un nombre premier Pa
Choisir un nombre Ya avec Ya<Pa
Choisir un troisieme nombre totalement quelconque qui sera la clef privée,
ici Clef_P_a
la clef publique et composé de Ya, Pa et d'un troisieme membre qui est
calculée en fonction de Ya, Pa et Clef_P_a
j'apelerai ce troisieme membre Delta_a
Delta_a = Ya^Clef_P_a (mod Pa) Ici le simbole ^ , coresspont au simbole
exposant
l'utilisateur A, peut difusée sa clef publique : Ya, Pa et Delta_a
Un utilisateur B veut envoyée des donnée a A mais pour cela il utilise un
Algo peu importe lequelle, mais il doit definir un clef que A pourra
retrouvée grace a sa clef privée
pour cela B recupere la clef publique de A et grace a sa clef privée
Clef_P_b il calcule la clef de cryptage ici K
K = Delta_A^Clef_P_b (mod Pa)
il crypte sont fichier a l'aide de la clef K.
puis il doit fournir à A une information qui lui permetrai de retrouvée la
clef
pour cela B vas calculer Delta_dec :
Delta_dec = Ya^Clef_P_b (modPa)
il envois donc à A les donnée cryptée et Delta_dec
A recois les donnée de B et le Delta_dec
A calcule alors la clef de decryptage :
K = Delta_dec^Clef_P_a (mod Pa)
puis decrypte les données
Bien sur cela ne fonction que si P est un nombre premier, et plus P est
grand plus la clef est dur a etre retrouvée pour toute personne tentant de
decryptée les données
"Sylvain SF" a écrit dans le message de news: 48c3f5be$0$908$
Talus wrote on 07/09/2008 10:46:
si vous avez des question sur mes algo qui pourrai vous aidez, je vous les transmettrai
certainement ! soit utiliser "encrypt" et "wrap" bien que sur une branche fr. de usenet, soit ne pas utiliser le néologisme barbare crypter qui ne veut rien dire.
par ailleurs, lever un doute: vous dites avoir mis au point une variante de DH mais chercher une fonction expliquant (pas à pas?) la vérification de primalité, les compétences pour la première condition n'incluerait pas la seconde ?
Sylvain.
DH est juste une methode permetant de definir une clef sans que celle ci soit difusée.
voila le principe de DH, enfin le principe derivée que j'ai etabli avec DH
Choisir un nombre premier Pa Choisir un nombre Ya avec Ya<Pa Choisir un troisieme nombre totalement quelconque qui sera la clef privée, ici Clef_P_a
la clef publique et composé de Ya, Pa et d'un troisieme membre qui est calculée en fonction de Ya, Pa et Clef_P_a j'apelerai ce troisieme membre Delta_a
Delta_a = Ya^Clef_P_a (mod Pa) Ici le simbole ^ , coresspont au simbole exposant
l'utilisateur A, peut difusée sa clef publique : Ya, Pa et Delta_a
Un utilisateur B veut envoyée des donnée a A mais pour cela il utilise un Algo peu importe lequelle, mais il doit definir un clef que A pourra retrouvée grace a sa clef privée
pour cela B recupere la clef publique de A et grace a sa clef privée Clef_P_b il calcule la clef de cryptage ici K
K = Delta_A^Clef_P_b (mod Pa)
il crypte sont fichier a l'aide de la clef K.
puis il doit fournir à A une information qui lui permetrai de retrouvée la clef pour cela B vas calculer Delta_dec :
Delta_dec = Ya^Clef_P_b (modPa)
il envois donc à A les donnée cryptée et Delta_dec
A recois les donnée de B et le Delta_dec A calcule alors la clef de decryptage :
K = Delta_dec^Clef_P_a (mod Pa)
puis decrypte les données
Bien sur cela ne fonction que si P est un nombre premier, et plus P est grand plus la clef est dur a etre retrouvée pour toute personne tentant de decryptée les données
Sylvain SF
Antys wrote on 07/09/2008 18:34:
Si, c'est d'usage courant: (pour les chaînes TV notamment)
tu as tout dit.
le PO voulait parler de cryptologie semble-t-il, pas de boite-à-con.
Sylvain.
Antys wrote on 07/09/2008 18:34:
Si, c'est d'usage courant: (pour les chaînes TV notamment)
tu as tout dit.
le PO voulait parler de cryptologie semble-t-il, pas de boite-à-con.
Si, c'est d'usage courant: (pour les chaînes TV notamment)
tu as tout dit.
le PO voulait parler de cryptologie semble-t-il, pas de boite-à-con.
Sylvain.
Talus
"Sylvain SF" a écrit dans le message de news: 48c40e52$0$880$
Antys wrote on 07/09/2008 18:34:
Si, c'est d'usage courant: (pour les chaînes TV notamment)
tu as tout dit.
le PO voulait parler de cryptologie semble-t-il, pas de boite-à-con.
Sylvain.
la cryptologie c'ets un science regroupant deux principale activitée
la cryptographie qui est la conception de code secret et le cryptage de donnée la cryptanalise qui consite a cassez les code secret et a decrypter par force des donnée cryptées
"Sylvain SF" <sylvain@boiteaspam.info> a écrit dans le message de news:
48c40e52$0$880$ba4acef3@news.orange.fr...
Antys wrote on 07/09/2008 18:34:
Si, c'est d'usage courant: (pour les chaînes TV notamment)
tu as tout dit.
le PO voulait parler de cryptologie semble-t-il, pas de boite-à-con.
Sylvain.
la cryptologie c'ets un science regroupant deux principale activitée
la cryptographie qui est la conception de code secret et le cryptage de
donnée
la cryptanalise qui consite a cassez les code secret et a decrypter par
force des donnée cryptées
"Sylvain SF" a écrit dans le message de news: 48c40e52$0$880$
Antys wrote on 07/09/2008 18:34:
Si, c'est d'usage courant: (pour les chaînes TV notamment)
tu as tout dit.
le PO voulait parler de cryptologie semble-t-il, pas de boite-à-con.
Sylvain.
la cryptologie c'ets un science regroupant deux principale activitée
la cryptographie qui est la conception de code secret et le cryptage de donnée la cryptanalise qui consite a cassez les code secret et a decrypter par force des donnée cryptées