GENERATEUR DE NOMBRES PREMIERS
cs_Anthomicro
Messages postés
9433
Date d'inscription
mardi 9 octobre 2001
Statut
Membre
Dernière intervention
13 avril 2007
-
21 janv. 2005 à 17:36
cs_Kirua Messages postés 3006 Date d'inscription dimanche 14 avril 2002 Statut Membre Dernière intervention 31 décembre 2008 - 1 avril 2007 à 13:48
cs_Kirua Messages postés 3006 Date d'inscription dimanche 14 avril 2002 Statut Membre Dernière intervention 31 décembre 2008 - 1 avril 2007 à 13:48
Cette discussion concerne un article du site. Pour la consulter dans son contexte d'origine, cliquez sur le lien ci-dessous.
https://codes-sources.commentcamarche.net/source/28972-generateur-de-nombres-premiers
https://codes-sources.commentcamarche.net/source/28972-generateur-de-nombres-premiers
1 avril 2007 à 13:48
1 avril 2007 à 01:24
1 avril 2007 à 00:11
Ton code est tres bien et te laisse pas deboussoller par des br**** avec des commantaire decalés
14 mars 2006 à 20:03
14 mars 2006 à 17:34
"C'est compliqué d'agir avec l'infini... faut voir comment on le défini." ^_^...
3 sept. 2005 à 13:10
3 sept. 2005 à 12:59
http://www.lifl.fr/~wegrzyno/Mersenne/mersenne1.html
2^3021377-1 est selon ce site, le plus grand nombre premier connu... je croyais que c'était plus grand...
j'ai 512 mo de ram, ma ram peut donc acceuillir 512*8*1024*1024 bits, soit 4294967296, je pourrais donc théoriquement acceuillir plus de 1000 nombres premiers de cet ordre de grandeur... c'est le cpu qui ramerais pour trouver un tel nombre
http://forums.futura-sciences.com/thread41127.html
3 sept. 2005 à 12:41
3 sept. 2005 à 08:47
3 sept. 2005 à 02:52
16 août 2005 à 13:09
2^2-1=3
2^3-1=7
2^5-1=31
le plus grand nombre premier calculé est un nombre de fermat...
La crypto quantique est effectivement une question de matèriel, mais elle pourrait bien (pour une organisation comme la CIA) remplacer la crypto asymétrique...
l'avantage du symétrique syr l'assymétrique, c'est la vitesse de calcul, l'avantage de l'asymétrique, c'est l'échange des clefs, donc, on se sert de l'asymétrique pour crypter des clefs symétriques et ensuite, on parles en symétrique...
La crypto quantique offre un avantage non négligeable : quand un espion lit un passage du message, ce message ne peut être renvoyé avec les mêmes caractèristiques...
la crypto quantique permetrait un échange de clefs vraiment inviolable : si on est espionné, alors on est au courant, et on procède à un nouvel échange de clefs symétriques... on n'utilises des clefs symétriques que si on n'a pas été espionné...
16 août 2005 à 13:00
La crypto quantique c'est un probleme hardware si je ne m'abuse... mais soit.
16 août 2005 à 12:23
16 août 2005 à 12:02
15 août 2005 à 21:14
13 août 2005 à 16:15
Je crois que tu mélanges un peu. La quantique, c'est pour l'échange de clés dans la crypto sym, c'est tout (si j'ose dire "c'est tout" :)).
Quoi qu'il en soit, l'asym a encore de beaux jours devant elle!
13 août 2005 à 16:10
les nombres classiques (premiers) de plus de 1024 bits sont vraiment interessants pour la crypto RSA...
mais la crypto quantique va bientot bouffer l'assymétrique...
13 août 2005 à 15:30
Alors 100 chiffres... hem...avec gmp, je pense que le problème est réglé vite fait!
13 août 2005 à 15:26
tu sais que si tu trouves un nombre premier d'au moins 100 chifrees la CIA te l'achetes 10 000 $ (enfin j'ai vu ca dans un livre) ?
Ca leur sert evidemment en cryptographie ...
24 janv. 2005 à 20:33
24 janv. 2005 à 20:32
24 janv. 2005 à 20:29
signed char : {-127;128}
|-127-128|=255
|0-255|=255
24 janv. 2005 à 20:29
Si les nombres sont signés (par défaut), sur 1 octet (8 bits) on peut coder les nombres de -128 à 127. Sur 4 octets (systèmes 32 bits), un nombre signé peut aller de -2 147 483 648 à 2 147 483 647.
Si les nombres sont non signés, sur 1 octet (8 bits), on peut coder les nombres de 0 à 255. Sur 4 octets (systèmes 32 bits), un nombre signé peut aller 0 à 4 294 967 296.
... http://www.aidejavascript.com/article121.html
24 janv. 2005 à 19:50
Ah bon ?
24 janv. 2005 à 10:54
Je ne monopoliserais pas toutes mes neurones sur ce point, qui bien que interessant, reste profondément inutile...
@+
23 janv. 2005 à 23:11
23 janv. 2005 à 22:48
23 janv. 2005 à 22:45
Tu dis "Tu considères que quand tu es à l'infini, tu peux encore avancer, or cela n'est vrai que si tu considères être, non pas à l'infini, mais à une "grande" valeur dans N"
FAUX! La preuve toute simple? Ok: limite pour x tendant vers l'infini de f(x) x, c'est l'infini, ok... bien... et limite pour x tendant vers l'infini de f(x) x+1, c'est combien??!! C'est l'infini aussi! CQFD, poils aux pieds!
Maintenant, je sais pas si on a le niveau pour ce débat. La mathématique de l'infini fait appel à des concepts qu'on apprend même pas à l'uni... en plus il faut différencier l'infini physique de l'infini mathématique...
Sur ce, à bon entendeur, salut!
;o)
23 janv. 2005 à 12:19
23 janv. 2005 à 12:15
23 janv. 2005 à 11:49
Prends au hasard 10000 nombres de Z, en gros tu en aura 50% qui sont aussi dans N...
En info on ne retrouve pas ça avec signed et unsigned car la borne se déplace...
22 janv. 2005 à 21:32
22 janv. 2005 à 21:30
22 janv. 2005 à 21:26
Je ne me souviens plus de la démonstration faite pour N et Z (on dit qu'ils sont dénombrables, allez savoir), mais prennons l'exemple de K, qu'on définira ici comme l'ensemble des carrés parfaits.
N = {0, 1, 2, 3, ...}
K = {0, 1, 4, 9, ...}
On peut associer à chaque élément de N un et un seul élément de K (en effet, soit n € N, n² € K pour tout n (€ = le signe "appartient à l'ensemble")).
On peut également associer à chaque élément de K un et un seul élément de N: soit k € K, sqrt(k) € N, pour tout k.
On se rend donc compte que les deux ensembles contiennent autant d'éléments l'un que l'autre, ce qui va complètement à l'encontre de notre perception intuitive (bah oui, entre 1 et 4 il y a 2 et 3, qui ne sont pas dans K mais bien dans N, et K est compris dans N, alors quoi??), mais le fait est que des travaux mathématiques déjà anciens mais tjs d'actualité, reconnus etc par les mathématiciens professionnels ammènent (et je ne comprends pas plus que vous) que si deux ensembles infinis peuvent être mis en bijection, ils contiennent une même infinité de membres, ce qui n'est pas vrai pour N et R par exemple.
La revue Math Jeunes n'est pas en ligne, malheureusement, et je n'ai pas de scanner :/ Je soulignerai seulement que je n'ai pas été franchement convaincu par l'article, mais ... ce que je vous présente ici, ce sont les conclusions du papier, et j'ai foi en cette revue.
22 janv. 2005 à 20:45
C'est mon avis mais je l'argumente ainsi: supposons que nous sommes à l'infini de N. Si on fait +1, on est à l'infini de N, si on poursuit avec des +1, on sera encore et toujours à l'infini de N et on aura dépassé celui de Z... etc... en d'autres termes, on ne peut pas traîter avec l'infini comme avec d'autres nombres... tout ça pour dire que l'infini de N est à la fois pareil et différent que celui de Z!!! Maintenant, pour R c'est à voir...
(vite, une aspirine!)
Si t'as l'URL, c'est volontiers!
22 janv. 2005 à 18:41
tout N est dans Z alros que le contraire est faux !!
22 janv. 2005 à 18:36
22 janv. 2005 à 18:32
je croyais plutot que tu renvoyais à la moitié de l'intervale N... Ce qui n'a aucun sens... N c'est la moitié de Z...
22 janv. 2005 à 17:05
22 janv. 2005 à 16:27
Ceci dit on s'en fout un peu, non??!!
;o)
22 janv. 2005 à 16:21
22 janv. 2005 à 16:02
les naturels vont le 0 à +infinit soit, ce demi axe n'existe pas, tu voulais surement parler de N N est une partie de Z (Zahl = entier relatif)...
22 janv. 2005 à 15:07
22 janv. 2005 à 14:33
"il peut arriver que ton programme en cherche un dans un intervalle qui n'en contient pas" dis-tu... un peu de maths:
Théorème des nombres premiers: Le nombre de nombres premiers =< à x, noté e(x), vérifie e(x) ~ x/lnx
Donc, supposons que je prenne dans mon algo l = 500. L'algo va donc chercher un nombres premiers dans l'intervalle [2^499,2^500]. Cet intervalle contient 1636695303948070935006594848413799576108
3210230215323947416456840480668982023372
7744163504616295207857544334206378003550
4608628272942696526664263794688 chiffres (tu peux vérifier sur http://www.swox.com/gmp/#TRY), ce qui est conséquent tout de même!
Un simple calcul nous dit que le nombre de nombres premiers entre 2^499 et 2^500 est:
2^500/ln2^500 - 2^499/ln2^499 (2^499/ln2)*(2/500 - 1/499) (2^499)* 0.00288... et je t'assure que ça fait bien plus que 1!
Pour ce qui est de l'efficacité, on peut être franchement plus rapide. Ne serait-ce qu'en utilisant GMP. En plus, les calculs ne sont pas faits sur des bits (on peut faire ça en PHP?), donc on perd du temps. Ceci mis à part, l'algorithme de Miller-Rabin est optimisé, ainsi que la fonction puissanceBigNbr (il s'agit d'une exponentiation de "droite à gauche").
22 janv. 2005 à 14:07
un inconvénient à ma méthode: les probabilités. s'il y a 150 nombres entre un premier Pa et un premier Pa+1, mais qu'il n'y en a que 85 entre un premier Pn et un premier Pn+1, alors Pa+1 sortira plus souvent que Pn+1, ce qui est une faiblesse exploitable par un cryptanalyste!
Juste au passage comme ça: on écrit algorIthmique, merci d'en prendre bonne note ;).
22 janv. 2005 à 09:23
Effectivement, ce code n'a que pour but de présenter Miller-Rabin, point final. Sinon il est vrai que avec GMP par exemple, il suffirait d'utiliser le PRNG gmp_random() puis gmp_prob_prime (qui utilise sûrement ce test) et ce serait fini!
Pour eXon...
merci pour l'info, j'suis pas trop au courant de ce qui existe comme fonctiones prédéfinies et j'ai pas pris le temps de chercher... je saurai pour la prochaine fois ;o)
22 janv. 2005 à 06:14
22 janv. 2005 à 01:22
Si tu vas sur cppfrance, tu verras que j'ai bien donné côté crypto... mais comme je préfère le php, je me suis mis en tête de refaire les mêmes choses... mais vu l'ambiance terrible que ça génère... enfin bon...
22 janv. 2005 à 00:09
21 janv. 2005 à 23:40
21 janv. 2005 à 23:17
C'est un test potentiellement inutile en php car :
Les variables php sont en float soit : 32 bits (ma calto te casse en quelques heures... Mon pc en quelques secondes...) Soit si qqn fait un code RSA c'est inutilisable... On est limité à 128 bits, alors autant les utiliser à fond...
c'est interessant pour l'algo, et non le code en lui même... ça met miller/rabin à portée de tout le monde...
Merci d'avoir posté ce code, je le referais surement en C++
21 janv. 2005 à 22:06
21 janv. 2005 à 22:03
mouais...
21 janv. 2005 à 21:59
je me permets encore, lol...
Encore une fois, je precise que je suis une brele pour ce qui est de faire un joli code. Mais j'apprends...
Alors, Malik, je t'aime bien (si si, j'aime bien tes remarques, tes excuses, le fait que tu ecoutes, que tu donnes ton avis)...je me fiche de ton code parce que moi, les nombres premiers, lol...
Mais c'est une jolie initiative :-)
Ceci dit, oui, le code HTML n'est pas bon (crade C tres pejoratif quand meme), pas W3C compliant. Mais ce n'est pas a toi que je veux ecrire, lol...juste : bravo Malik, t'as eu le courage de faire un source en demandant une critique d'Antho le terrible, et en plus, sur des maths!!
Non, je veux ecrire pour JulioDelphi : tu oublies un truc...le XHTML c'est un peu le HTML 5.0...non parce que si on suit ton raisonnement, on peut s'en tenir au HTML1.0, apres tout? Maintenant, c'est le XHTML. X pour Extended, et un peu quand meme pour XML...bref, en XML, la casse est importante! Ca, j'en sais quelquechose...ben autant s'habituer a ce que ca le devienne pour notre cher vieil HTML...moi je trouve ca bien, si on parle juste de casse. T'aimerais, toi, que dans ton code php, la variable $MaVariable soit la meme que ta variable $mavariable ? Moi pas...je te dis pas le bordel dans ton code si tu te permets d'ecrire tes variables avec la casse que tu veux...ou tes fonctions...ou tes classes...t'imagines? Un coup c'est la classe MaClasse, un coup c'est MACLASSE, un coup c'est ...enfin t'as compris.
Ensuite, se conformer au standard W3C, c'est faire avancer le web plus vite...a mon avis. Tu imagines creer un RSS sans suivre la bonne DTD? Tu t'imagines creer une requete SOAP sans l'enveloppe SOAP "standard" ?
Ok, le HTML, ca a ete iun peu tout et n'importequoi...parce qu'il a vite evolue, parce que les navigateurs en ont fait a leur tete (surtout un...suivez mon regard...mais c'est pas plus mal parfois puisque certaines de ses excentricites sont devenues des standards maintenant...), parce qu'il a ete trop permissif...mais maintenant, il devient rigoureux, serieux, plus utile, plus puissant...autant s'y conformer, ca ne peut que faire du bien a nos codes dans l'avenir. Enfin en tous cas, ca leur en donne un, d'avenir...
21 janv. 2005 à 19:02
a ++
21 janv. 2005 à 18:52
21 janv. 2005 à 18:29
"en HTML on a le loisir de choisir la casse de ses balises, ce n'est plus possible sous XHTML"... donc son code HTML est bon !
merci pour ton lien =)
ps : merci de ne pas insulter les gens de "porc" et de commenter la source pour le fond et non pour la forme ...
21 janv. 2005 à 18:27
Thanx ;o)
21 janv. 2005 à 18:24
www.vulgarisation-informatique.com/xhtml.php
ça devrait suffire ;-)
21 janv. 2005 à 18:10
21 janv. 2005 à 17:56
Après suis mon avis ou pas, perso je m'en fiche après tout, j'aurais fait mon devoir. Le seul truc à ne pas faire c'est, lorsque tu réponds à quelqu'un, de coder comme tu le fais actuellement, c'est tout...
Que tu codes comme un porc c'est un fait, mais ne codes pas comme un porc lorsque tu veux rendre service à la communauté puisque c'est l'effet inverse qui se produira à plus ou moins long terme, et après on sera toujours obligés de rabacher "en minuscules ceci, <?php au lieu de <?" à cause de gens comme toi...
21 janv. 2005 à 17:52
J'hallucine...
21 janv. 2005 à 17:42
21 janv. 2005 à 17:40
et d'utiliser des que tu utilises et moi jamais... par contre les echos, c'est vrai que j'ai brassé... mais #*&#* à la fin! Le but de ce code, c'est de présenter des fonctions... pas un affichage!
Un point pour toi par contre: je n'utilise jamais isset(), mais je devrais... je vais corriger...
21 janv. 2005 à 17:36
bon tu t'en doutais, le code html est crade...
Mais je n'ai pas envie de corriger, puisque tu as fait exprès de poster cette source sous cette forme.
Les echo sont aussi crades au passage, et tu ne vérifies nul part avec isset() si les variables $_POST sont présentes...