RECHERCHE DE NOMBRES PREMIERS

Commentaire de MadM@tt le 18/11/2004 18:14:38

PS : pour l'instant mon max est à 260 987 qui dit mieu ?

pour ceux que ça interesse des scientifiques en ont trouvé à x10^340 chiffres je crois, dans cet ordre de grandeur la

Si vous avez un meilleur algorithme a proposer, allez-y

Commentaire de MadM@tt le 18/11/2004 18:52:29

Pour crypter c'est essentiel :
quand tu prend 2 nombres premiers p et q (qui je le précise ne sont donc divisibles que par 1 ou par eux-meme) et que tu les multiplie : p*q
le produit p*q peut-etre rendu public et des fichiers peuvent etre codés avec, mais pour décoder il faudra se servir de p et q séparément.
Or l'avantage des nombres premiers multipliés ainsi, c'est que à partir du produit p*q il est extremement difficile de retrouver le p et le q du départ... (ça nécessite énormément d'ordis et de temps).

Donc en gros tu code avec p*q qui est public, et seulement l'utilisateur qui a la vraie clé : p et q séparément, peut décoder le fichier obligatoirement avec les 2 nombres séparés (c'est du à des calculs mathématiques assez compliqués)

euh chu pas un expert, jme suis peut etre trompé quelque part mais dans l'ensemble c'est ça

Commentaire de Pingouin le 18/11/2004 19:59:51

Salut,
Juste une petite amélioration de rien : j'ai vu que tu cherchais les diviseurs jusqu'a nombre /2 en fait on peut démontrer (mais c pas évident) qu'il suffit de s'arrêter a la racine carré du nombre, ca diminue sensiblement le nombre de calculs et améliore donc la vitesse, ce qui n'est pas négligeable dans ce genre de prog.
Sinon fais en quelque chose de bo graphiquement comme ca ca pourra en effet décorer le pc pdt kil ne fait rien...

@+

Pingouin

Commentaire de MadM@tt le 18/11/2004 20:24:54

oulala la vitesse est multipliée par 20 même plus merci Pingouin, sinon spy166 oui c'est le principe du cryptage RSA
par contre je me demande si quand j'arriverai à des nombres tellement grands qu'ils seront stockés sous la forme .....*10^n
est ce que ça me garde en mémoire tous les chiffres du nombre ou alors ça garde seulement l'expression ....*10^n ? si quelqu'un peut m'apporter une réponse

Commentaire de vlad2i le 18/11/2004 22:05:00

Oulala hehe c'est une méthode brutale pour trouver ca...

Quelques idées :

Un nombre premier x est forcément tel que x mod 4 = 3 ou x mod 4 = 1 et forcément tel que x mod 6 = 1 ou x mod 6 = 5 ca peut largement augmenter la vitesse de ta recherche (par exemple en fesant une boucle de I à I\6 et en testant la primalité des nombres 6*I+1 et 6*I-1)

Ensuite, éviter les nombres évidemment pairs, alias nombres pairs et multiples de 5 par exemple ...

Si tu veux vraiment un algorithme éfficace, j'ai un document de trois chercheurs indiens qui ont utilisé une intégrale de ramanujan pour étudier la congruence des nombres non premiers - et qui que quand il renvoie q'un nombre est premier c'est avec 100% de certitude (l'inverse n'est pas vrai par contre :))

Parce que pour RSA, la sécurité est faible en dessous de 300 chiffres, produit : 300×300 = 90000 chiffres pour le produit pq :) il faut donc que tu gères les grands chiffres :)

Vlad

Commentaire de vlad2i le 18/11/2004 22:20:11

Ton interpretation est exacte, mais cependant, tu devrais utiliser plutot

If  ((x mod 4 = 3 or x mod 4 = 1) and (x mod 6 = 1 or x mod 6 = 5)) Then
'La tu teste la primalité - la nombre est peut etre premier
else
'Le nombre n'est pas premier
endif

Car il se peut qu'un nombre ne soit pas premier mais passe le test qd meme, et là tu peux d'office tester (ce qui réduit considérablement les tests qd meme)

"quand tu parle de 100% de certitude, tu veux dire que l'algorithme (barbare c'est clair) que j'utilise n'est pas très fiable ?"

Non, en fait il est fiable, mais lent - je parlait de l'algorithme intégral, enfin peu importe

Vlad

Commentaire de Mindiell le 19/11/2004 16:33:06

Pour information, ton programme me donne ca au début :
1
5
7

Je suis au regret de te dire qu'il manque 2 et 3 comme nombres premiers. J'accorde le 1 bien qu'au point de vue mathématiques le 1 n'est pas premier pour des questions de généralisation de lois sur ces nombres...

Commentaire de vlad2i le 19/11/2004 16:46:07

J'ajoutes que pour optimiser d'avantage la vérification de primalité, tu devrais stocker les nombres premiers trouvés dans un tableau (ex: prems() ) qui contient les premiers a partir de 3 inclus et pour tester

Function TestPremier(x)
     If X mod 2 = 0 then PasPremier

     For I = 0 to ubound(prems)
          If prems(I)<int(sqr(x)) then
               If X mod Prems(I) = 0 then
                    PasPremier
                    Exit Function
               Endif
          endif
     next

     Premier
     redim preserve prems(ubound(prems)+1)
     prems(ubound(prems)) = X
End Function

Par exemple :)

Vlad

Commentaire de Pingouin le 19/11/2004 19:34:23

Hugh !
Ben ecoute ca fait plaisir de servir a quelque chose de temps a autres.
Sinon je vois que ca a pas mal progressé depuis mon dernier passage !! En effet quelques tests préliminaires ne sont pas a négligés surtout pour de grands nombres. Encore quelques secondes de gagnées !
Sinon je vais essayer de voir si je le retrouve mais il serait intéressant d'implémanter le dernier algorithme a ce sujet qui nous vient de deux mathématiciens indiens qui parait il est une preuve mathématik mais pas forcement bcp plus rapide voire plus lent d'apres ce que j'ai entendu dire. si kkun voit de koi je veux parler kil n'hésite pas...
Voila voila,
Bonne continuation j'essaierais de garder un oeil la dessus ca m'interesse.

Commentaire de vlad2i le 19/11/2004 22:47:54

Désolé l'ami hehe ton implémentation (ton changement) ne sert à rien :)

For I = 0 to int(sqr(ubound(prems)))+1 <= inutile et innefficace - tu comprends je crois que prems contient les nombres premiers trouvés (exemple prems(4) = 13 ) et que j'avais déjà pensé a mettre "If prems(I)<int(sqr(x)) then" une ligne en dessous :)

Bien essayé :)

Par contre, Pingouin : la formule de Ramanujan permet de tester la primalité de nombres de plusieurs millions de chiffres (binaires) en quelques secondes :) donc plus lent c'est discutable :)

Vlad

Commentaire de Mindiell le 20/11/2004 02:18:09

MadMatt, tu peux te rendre compte que la plupart des nombres non premiers sont divisibles par les petits nombres premiers. Donc en créant ton tableau Prems en le faisant contenir les 200 premiers nombres premiers tu élimineras par exemple déjà un grand nombre de nombres pas premiers, et ensuite tu appliques ta méthode brutale par exemple :)

Commentaire de crazyjoke le 20/11/2004 22:23:03

Pour la racine du nombre a tester, l'expliquation est facilement concevable :

Un nombre, si il n'est pas premier possède au moins un couple de multiples comme celui ci

a*b

avec a>b et a <> 0, alors il possède aussi comme multiple le couple :

b*a

Il faut donc s'arrêter à la racine carrée : quand a=b; toutes les recherches après sont vaines :).

Commentaire de sibi12 le 22/11/2004 16:01:50

Arf j'avais plein de suggestion en regardant ton code mais je vois qu'on te les a deja tte donnée (même l'explication pr la racine carré)..
J'ai fait un programme du style il y a quelque temps mais je ne le retrouve plus j'ai du l'effacer lors du gd nettoyage :(...

Sinon pour l'idée du tableau je l'avais implémenter, ça prens pas mal de place en mémoire mais le gain de temps est interressant. Pour repondre à ta question avec les grand nombre, si tu t'ai déjà interesser à la représentation en memoire tu devrai savoir qu'un entier sous VB est codé sur 32 bit et est signé. la plage est donc de -2^31 à 2^31-1.

La fpu (floating point unit ou coprocesseur arthmetique) permet de jouer avec des entiers sur 64 bit et qui ont dc une plage si on compte seulement les positif jusque 2^64-1 soit +- 1.8 * 10^19. Le problème est que VB n'implémente qu'une version modifier : le Currency. il décale la valeur de 10 000.  je ne sais plus si cette implemantation est signée ou non mais son max ne depassera de toute facon pas 1.8*10^15 et tu va perdre pas mal de temps.

Si tu veux quelque chose efficace pour un eventuelle RSA je te conseille de te tourner vers le C++ et d'utiliser sa librairie ZZ (une tite recherche sur google pour la trouver).

Pour l'algo des 3 indiens c'est utile uniquement pour les très grand nombre et n'est pas trivial a implémenter. la premiere condition à vérifier est que le nombre ne peux pas s'écrire sous la forme n=a^b ou un truc du style.

Il y a un autre algo fort utiliser pour le RSA c'est Miller-Rabin qui se base sur des nombre aléatoire mais il ne donne qu'une probabilité si le nombre est premier. Si le test dit que le nombre n'est pas premier c sur a 100% sinon la probabilité qu'il ne soit pas premier est de 1/4. en repetant le test n fois la probabilité sera de (1/4)^n. on peux donc être amplement satisfait après une 20aine de test (1 chance sur 4^20 soit 1 sur +- 10^12)

voilà si t'as des question je m'etait pas mal renseigner sur les nombre premiers. Le plus rapide est sans doute Erathostene mais inaplicable sur des grand nombre.

Commentaire de Mindiell le 22/11/2004 17:42:13

un tableau représentant tous les impairs ?

Le problème, c'est que s'il veut diviser rapidement son nombre a tester par les 100 premiers "nombres premiers", il doit les retrouver, non ? L'avantage du tableau "horrible" c'est qu'il contient les 100 premiers :o)

Pour Erathostene, tu pourrais mieux expliquer ? J'ai pas le temps de faire de recherche, mais j'aimerais comprendre le truc quand meme ;o)

Commentaire de Mindiell le 22/11/2004 18:01:49

Donc un tableau de 100 millions de bits ? Marrant comme procédé, je connaissais pas.

Par contre, pour tester si un grand nombre est premier ou pas, ca marche plus du tout (ou alors faut y aller)...

Commentaire de sibi12 le 22/11/2004 18:18:26

Non comme j'ai dit Erathostene est inapplicable pour les grand nombre.  Une source sur cppfrance implementai vraiment bien erathostene mais je tombe plus dessus... si je la retrouve je vous fais signe

Commentaire de Mindiell le 22/11/2004 18:22:20

On est d'accord pour le stock de tous les nombres premiers, ca devient délirant. mais si c'était pour accélérer la fonction "est-ce un nombre premier", je pense que mon idée peut donner un compromis intéressant (tableau de 100 voire 200 premiers nombres premiers)...

Ceci dit, le crible d'erathostene m'intrigue, je vais me pencher dessus :)

Commentaire de Mindiell le 22/11/2004 18:29:30

86 125 647 est divisble par 3... hum ;op

Commentaire de MadM@tt le 22/11/2004 21:48:11

Oula ça ma fait bcp de mails en un jour ça, ne paniquont pas
zoslex > yes bonne idée, vu le gain de temps je vais vite mettre ça au point
Pour les autres à propos des grands nombres j'ai encore jamais regardé mais je me pencherai bien dessus
Sinon au niveau du crible d'erastosthene et patati et patata vous etes sur que ça peut permettre de gagner du temps ? Parce que ça a l'air compliqué et pour moi qui dit compliqué du beaucoup de calculs donc un temps long, enfin je dit ça sans avoir jamais testé quoi....

sinon merci à tous pour vos commentaires

PS : j'essayerai bien de mettre cette source en C++ ou C#, mais est ce que le C# est aussi rapide que le C++ ?

Commentaire de MadM@tt le 22/11/2004 21:58:30

Oui j'ai vu ça mais j'entendais aussi la formule de Ramanujan et le tableau des 100 ou 200 nombres premiers dans le lot
Mais le problème des grands nombres reste encore je vais essayer de regarder ça si je trouve du temps

Commentaire de vlad2i le 22/11/2004 22:46:40

"Vlad2i > Erathostene est surtout rapide pour avoir tout le nombre premier de 1 à n.
il est surtout plus rapide car on ne fait aucune division et 5 6 addition seront tjs plus rapide que 1 modulo(le modulo a la meme instruction machine que la division)"

Eratostene consiste a éliminer les nombres en fonctions des modulos, pas en fonction des additions... on ne fait pas d'additions me semble-t-il

Enfin si ma mémoire n'est pas encore totalement décrépie...

Vlad

Commentaire de MadM@tt le 23/11/2004 00:05:25

zoslex > Ton idée de ne pas ajouter dans la liste les nombres trouvés n'apporte aucun gain de temps (visible). En effet tu a surement du supprimer la ligne qui ajoutait le nombre à la liste si il était premier afin de voir si c'était plus rapide, mais ce n'est pas le fait de l'ajouter dans la liste qui prend du temps, mais plutot de savoir s'il est premier ou pas.
J'ai essayé plusieurs méthode pour stocker les resultats dans une chaine de caractère, un tableau, mais pas de changement de vitesse significatif.... à moins que j'ai mal compris ce que tu voulais dire....
mais merci d'avoir proposé l'idée quand meme
@ +

Commentaire de Mindiell le 23/11/2004 00:16:53

désolé dnob700, et on n'est pas la pour lancer une polémique, mais de nos jours, les compilateurs donnent des vitesses équivalentes...

MadM@tt, en effet, ne pas utiliser ta liste de gauche accélère de beaucoup le calcul quand tu en fais un long...A priori, ca le fait même planter au bout d'un moment (Textbox trop petite...)

Commentaire de zoslex le 23/11/2004 17:29:40

Je ne vois pas ce que tu aurais pu mal comprendre.
Le gain est largment visible... Je pense que la perte est constante puisque dû à la perte de temps d'afficher en permanence.
Ce que j'ai changé :


' Procédure qui cherche les nombres premiers
Private Function CherchePremier()
    Dim Number As Double

    'zoslex
    Me.Liste.Visible = False
    
    Me.Caption = "Recherche ... - MadMatt"


puis à la fin de la fonction :


    Me.Caption = "Fini !"
    
    'zoslex
    Me.Liste.Visible = True
    
End Function


Merci de dire si tu vois mieux, ou si tu ne vois toujours rien.
Préviens si tu mets à jour, que je télécharge la dernière version, merci :)

Commentaire de sibi12 le 23/11/2004 19:24:08

vlad2i > je ne comprend pas pkoi tu dis que la methode classique en verifiant si tout les nombres de 1 à n sont premier est plus rapide... chaque addition te permet de verifier si un nombre est premier. on cherche pas le modulo, c'est pas le nombre d'addition qu'on cherche. je reste persuader que pour trouver tout les nombre premier de 1 à n c le plus rapide (pour une valeur raisonnable de n sinon les nombre premier s'espace de plus en plus et beaucoup d'addition ne serve plus a rien)

je me disai la même chose du CLR au debut mais en y regardant de plus près le jit fais qu'on a un code plus ou moins aussi rapide que du C++. l'idéal pour le verifier serai de faire un sgen sur un prog .Net et voir

Commentaire de dnob700 le 23/11/2004 20:07:51

je me suis mal exprimé, mais le VB.NET compile pour le clr aussi, et non plus pour la machine virtuel visual basic comme le faisait VB6, c'est donc exactement la même chose que du C#

ce qui n'est par le cas du C++ compilé pour win32 (faites l'essai, je ne veut pas lancer de polémique, mais c'est vraiment plus rapide).

pour ce qui est des nombres premiers, il y a ces deux pdf qui sont très bon si vous êtes un peu interessé par de la théorie :

http://perso.wanadoo.fr/sectionpc/tpe_cryptage/crypto/pdfs/primalite.pdf (en français)

http://perso.wanadoo.fr/sectionpc/tpe_cryptage/crypto/pdfs/primality.pdf (en anglais)

Commentaire de MadM@tt le 23/11/2004 22:08:54

zoslex > oui je n'avais pas compris, j'ai essayé ton code mais je n'ai pas trouvé d'amélioration vraiment flagrante, tu trouve vraiment que ça va plus vite toi ??

Vlad > Je vais tester avec LockWindowUpdate

dnob700 > merci pour tes pdf je vais y faire un tour

vous savez que tout les soirs ma boite hotmail est prete à exploser avec tous les commentaires que vous envoyez... 20 mails par ci, 15 par la
Mais continuez !!! On avance !

@ + tous

Commentaire de zoslex le 24/11/2004 14:23:47

J'ai poussé un peu plus loin les investigations. Cacher la liste me fait gagner 40% du temps de calcul.

Je m'explique... Je suis arrivé aux alentours de 150 000 000 avec un fichier de 92 Mo. Le temps est en deux parties : le calcul et la sauvegarde.
- Le calcul avec mise dans la liste : la cacher avec Me.Liste.Visible donne 40% de gain (6s au lieu de 10s).
- La sauvegarde : ça me prend 35s de faire Save.

Alors, avec autant de temps pris pour la mise sur disque dur par rapport au calcul à proprement parler, je me demandais le pourquoi du 99 999.

Ne peut-on pas augmenter ce nombre ? Quelle est sa limite ?

Commentaire de MadM@tt le 24/11/2004 17:26:47

2 questions très pertinentes comme dirai mon prof de filo lol

Mindiell > Tu aimerais un programme qui travaille et que tu ne puisse pas voir le résultat, enfin c'est vrai que je pourrai ajouter une option pour cacher ou pas la liste, je vais étudier ça

zoslex > Comme je viens de le dire, je vais donc ajouter l'option pour cacher ou montrer la liste, comme ça si on laisse tourner le prog pendant 1h quand on est pas la, autant cacher la liste, et si on veut on  pourra la voir
Sinon pour ta question à propos du nombre 99 999, la réponse est simple :
c'est un nombre pris au hasard, ni trop grand ni trop petit, je m'explique. Au départ le programme calculait comme un fou et mettait tout dans la listbox, et il sauvegardait quand on l'arretai. Sauf que si ton ordi plantait tes progrès étaient effacés, et au bout d'un moment ça commence à prendre de la place en mémoire, ce qui peut ralentir encore + le programme (et en + au moins tu voit l'avancement, alors qu'avant tu ne voyais pas apparaitre les nouveau nombres).
C'est pourquoi tous les 99 999 nombres, tout est rafraichit, on avance par étape en fait, et bien sur ce nombre peut etre changé, je l'ai pris pour pas que le rafraichissement soit trop fréquent, ni trop espacé.

voilà

Commentaire de MadM@tt le 24/11/2004 18:22:55

Mon fichier fait 320 Mo, j'ai voulu l'ouvrir mais je n'avais pas fait attention à la taille et ça ma mis ma mémoire vive à 0% libre et mon fichier SWAP à 10 % (et encore j'ai terminé le processus).
Comme quoi au bout d'un moment tout tes résultats, il ne vaut mieux pas avoir envie de les voir tous d'un coup :(

Commentaire de MadM@tt le 24/11/2004 21:33:20

mdr bonne question, je pourrai peut-etre essayer de faire un lecteur spécial, qui ne lit que les premieres lignes, puis quand on descend ça charge les suivantes, enfin je ne sais pas encore...

Commentaire de BruNews le 24/11/2004 22:35:57 administrateur CS

RECTIF: suffit d'un ZERO binaire au cul de chaque nbr et le tour est joue pour une lecture en tres haute performance, on gagne toujours 1 octet par nbr au niveau du fichier. Faudrait par contre pouvoir utiliser les pointeurs, alors ecris toi une dll C pour faire la lecture....

Commentaire de BruNews le 25/11/2004 00:01:33 administrateur CS

deja que les Long de VB sont sur 31 bits, il ira pas loin dans l'enumeration en ce cas, big probleme...

Commentaire de Mindiell le 25/11/2004 00:27:48

Perso je stockerais 1 million de chiffres par fichier en changeant de fichier de temps en temps :)

Commentaire de Pingouin le 25/11/2004 20:19:00

Ah me'de alors j'etais passé rien que pour te proposer de découper en plusieurs fichiers de petite taille... Bon ben c raté pour ce coup ci lol.
Et pourquoi pas proposer une option pour ne stocker kun certain nombre, parmi les derniers...
Sinon je ne suis pas un spécialiste mais vous croyez qu'il y a moyen de travailler sur des strings pour s'affranchir de la limite de taille des long ? Mais c sur ke la il te faudrait faire toi meme les opérations .... C'est ptet a voir non ?

Commentaire de sibi12 le 26/11/2004 17:14:45

Ouch des string tu va perdre enormement en rapidité. je te conseil plutôt un tableau de long ou de byte. Mais si tu veux quelque chose de vraiment efficace ==> C++

Commentaire de sibi12 le 26/11/2004 19:55:17

bah un tableau de long pour jouer directement sur 4 octets les operations sont les meme que ce soit 8 ou 32 bit ca accelere les calculs.

ui C/C++ idem ;-)

J'avais déjà entendu parler de ca. ca fait qd même 33Mo rien que pour stocker le nombre !! mais il y a des technique beaucoup plus sofistiquer style champ de mersene et tout ca...

Commentaire de Mindiell le 27/11/2004 05:05:29

sibi12> un tableau de long au lieu d'un tableau d'octet c'est de la place de perdue, non ? un octet suffit a stocker nu chiffre entre 0 et 9.

Ces fameux chiffres énormes sont des nombres de Mersenne, donc pour les stocker pas besoin de grand chose :) ca donne ca : Mn = 2n - 1 (comprendre 2 puissance n), il suffit donc de connaitre n. Malheureusement ils ne sont pas tous premiers :o)

Commentaire de Pingouin le 27/11/2004 13:25:48

Les nombres de Mersenne ne sont pas les seuls nombres premiers a plusieurs millions de chiffres. Je crois que l'un des plus grand doit s'ecrire 2^61-1 ou un truc dans ce genre.
MadM@tt >> Si tu arrives a construire un ensemble de fonctions mathematiques de ce type moi je m'emballe. Ce qui est dommage c'est que je ne suis pas sur d'avoir le temps suffisant pour te proposer mon aide mais on ne sait jms donc si tu as besoin n'hésites pas...
bon courage

Pingouin

Commentaire de Mindiell le 27/11/2004 15:31:39

Euh pingouin, le plus grand nombre premier est de la forme 2^n-1 et ca c'est la forme de Mersenne.
Et celui dont je parlais vaut ca : 2^24 036 583 -1

Oui, oui, 2 puissance 24 millions :o)

Commentaire de sibi12 le 27/11/2004 16:34:32

Si si tout les nombre de mersenne sont premier !!! mais on ne les connait pas tous.

le theorme dit :

M = 2^p - 1

Si M est premier

alors p est premier

http://membres.lycos.fr/villemingerard/Premier/record.htm#Mersenne

Commentaire de Pingouin le 27/11/2004 18:57:14

Euh ouais je comprend pas bien ton dernier post. Mais avec p=4 ca me donne 2^4=16 et donc M=2^4-1=15=5*3 ca m'a tout l'air d'un nombre de Mersenne mais pas d'un nombre premier donc a priori tous ne sont pas premiers.
Par contre si p est premier la oui je ne dis pas. Par contre tu as sans doute vu sur ce site que si on a un nombre de Mersenne on en a immédiatement un parfait !! Kan est ce que ce code (qui recueille un sacré paquet de commentaires kanm^m!!) détectera les nombres de Mersenne ?

Commentaire de Mindiell le 27/11/2004 19:57:58

Alors pour info, les nombres de Mersenne sont de la forme Mp = 2^p -1 avec p premier...
et tous les nombres de Mersenne ne sont pas premiers : M11 ne l'est pas.

Volia...

Commentaire de Mindiell le 27/11/2004 20:34:16

Oui, euh donc un Mersenne n'est pas forcément premier, c'est ca ? on est ok ? :o)

Pour les longs chiffres, je vais tenter une petite classe en C, ca me parait beaucoup plus pratique :o)

Commentaire de MadM@tt le 28/11/2004 12:19:46

Ah ouai merci j'ai compris l'histoire des nombres de Mersenne, mais alors à quoi ils servent ? à trouver des nombres premiers ?

Commentaire de MadM@tt le 28/11/2004 12:30:47

ah ouai donc on pourrait se servir de ça pour trouver des nombres premiers c'est ça ? par exemple en faisant un programme qui calcule un nombre de mersenne et vérifie ensuite s'il est premier, on aurait beaucoup plus de chance d'en trouver qu'en faisant une recherche exhaustive.

Commentaire de sibi12 le 28/11/2004 12:52:24

C'est ça en fait ces nombre ont plus de chance d'etre premier qu'un nombre aux hasard mais apparement plus on mon te ds les valeur plus ils sont rare. on pense que 2^24 036 583 -1 est le 41 eme !!!

je viens de penser à un truc. si un nombre de mersenne est de la forme 2^p-1 on est pas obliger de le representer en mémoire puisque en base 2 une suite de p 1. il doit y avoire moyen d'extrapoler quelque chose de ça pour faire des modulo rapide...par ex :

(je fait les calculs en live :p)

mod 3 : 0 si n est pair  1 si impair donc c = p mod 2
mod 5 : si on prend p =1,2,3,... c une suite de 1,3,2,0, 1,3,2,0,....
mod 7 : 1,3,0, 1,3,0,...

en fait si on arrive à montrer que c'est tjs une suite suffit de cherche p mod premier_0_de_la_suite. si c'est 0 n n'est pas premier sinon on continue la boucle !!!

d'accord je l'accorde c'est pas super simple à coder mais on pourrait chercher mathematiquement avant de coder à la bourrin

Commentaire de Mindiell le 28/11/2004 13:48:56

sibi12> Si ca peut t'aider, n'oublie pas que les nombres de la forme 2^p -1 sont, en binaires, une suite de p bits tous à 1. Pour les Mersennes, ca sera donc une suite de p bits avec p premier :
1
11
111
11111
1111111
11111111111 (11, pas premier)
etc... :o)

Commentaire de Mindiell le 28/11/2004 14:10:03

oups, bien entendu, 1 n'est pas bon :o)

Commentaire de MadM@tt le 28/11/2004 14:21:23

Pour les nombres de mersenne je crois avoir compris, mais alors j'ai juste à prendre un nombre du style 1111111, tester s'il est premier, si oui je calcule 2^p -1 et je teste si ça c'est premier ? c'est simple non ?

et alors (j'ai vu ça sur tes liens sibi12) quand on parle de Mersenne 41, ça veut dire que le nombre p est constitué de 41  "1" ?

Commentaire de sibi12 le 28/11/2004 14:28:32

Mindiell > Oui oui j'y ai penser... ;-)

Commentaire de vlad2i le 28/11/2004 14:47:50

Plus de 100 commentaires ... tu bats des records déja

Pour compléter les nombres de mesrennes et leur lien avec des parfaits : le seul nombre premier, impair et parfait serait supérieur à 10^300 et contiendrait plus de 70 facteurs premiers et serait un nombre de mesrenne...

Bonne chance a celui qui le trouve...

Vlad

Commentaire de sibi12 le 28/11/2004 16:32:35

Vlad > non c'est pas valable pour n'importe quelle nombre si on prend ceux de la forme n^n mod 5 la série ne se repete pas :
1,4,2,1,0,1,3,1,4,0,1,1,...

mais effectivement puisque 2^p est une progression geometrique de raison 2, ca marche pour 2^p et si ca marche pour 2^p mod n et que (2^p-1) mod n = ((2^p mod n)-1 mod n) et ca marche aussi (les 0 de la serie deviendront n-1 et les autres seront diminuer de 1 mais la serie reste intact).

Commentaire de Pingouin le 28/11/2004 18:15:33

Qui eut cru qu'un simple bout de code pour chercher des nombres premiers nous aurait emmener si loin ?!!! La j'avoue que je n'ai pas le nivo en arithmétique pour faire avancer le schmilimilimiliblick mais je me demandais qu'elle utilité trouver à ces quelques nombres mis a part RSA et ses nombres astronomiques ?

Commentaire de MadM@tt le 28/11/2004 18:29:58

Ouais ! vive nous qu'on cherche ce qui sert à rien lol !

Commentaire de Pingouin le 28/11/2004 20:42:50

Ah et au fait je participe au programme de recherche des nombres de Mersenne dont j'ai parlé comme koi je suis convaincu et puis le calcul des decimales de Pi a un interet théorik important.

Commentaire de vlad2i le 29/11/2004 17:32:45

"si le seul nombre parfait impair est supérieur a 10^300 on le connait" > non évidemment ...

"il semble improbable qu'un nobre parfait soit impair"> ca ne veut pas dire impossible...

Je surenchéris : pi et les nombres premiers, comme e et la plupart des constantes irrationneles transcendantes sont ABSOLUMENT NECESSAIRES ne serait ce que pour connaitre avant de comprendre ce qui dépasse la logique humaine :p

Rien n'est inutile, de plus, et pi comme e comme les nombres premiers sont à la base de nos math modernes (cos, sin, racine et j'en passe) et bien que nous n'égalerons jamais nos (z) ainés rien n'empeche de suivre leurs traces, c'est peut etre d'ailleurs le meilleur moyen de les surpasser...

non ?

Vlad

Commentaire de Mindiell le 29/11/2004 17:51:58

Mea culpa, supérieur à 10^300 ne donne pas de limite supéreure, donc mise à part l'affirmation que c'est un nombre premier qui contient des facteurs (ca c'est impossible :o) ), ton affirmation ne peut-être que vraie... mais vraiment improbable (si c'est un Mersenne).
Si ce n'est pas un Mersenne, on l'a peut-être déjà dépassé.

D'ailleurs, en y réfléchissant, un nombre parfait ne peut pas être premier puisqu'il vaut la somme de ses facteurs !!! :o)

Je reprends donc ton affirmation : "Un nombre impair et parfait existe peut-être..." :o)

D'ailleurs, s'il en existe au moins un, je doute qu'il n'en existe pas plusieurs....

Commentaire de Mindiell le 29/11/2004 18:13:00

Tu as un lien STP ? :o)

Commentaire de Mindiell le 29/11/2004 18:27:14

"il serait premier, impair, parfait"
Ca te gene pas cette affirmation quand meme ? Un premier qui est parfait ?????

Commentaire de MadM@tt le 29/11/2004 18:35:37

Ahhh jme disais bien aussi, je comprenais pas pourquoi tu parlais en meme temps de nombres premiers et de nombres parfaits... J'allais perdre le fil

Commentaire de MadM@tt le 29/11/2004 18:41:10

Oula, mais pourquoi ce nombre la précisément, a t'il une utilité ? (sans retourner dans le débat de l'utilité de faire de tels calculs)

Commentaire de vlad2i le 29/11/2004 18:45:10

Ce nombre est juste cherché depuis descartes.... en dehors de ca, pi est cherché depuis plus de 2500 ans et les nombres premiers depuis pythagore...

Vlad

Commentaire de MadM@tt le 29/11/2004 19:05:49

ah ok, seulement la c'est pas comme pi, on en connais aucun bout c'est ça ?

Commentaire de dnob700 le 29/11/2004 19:16:09

pas sur que Pi ne se répète jamais.

Ca voudrait dire que Pi est un nombre normal, et même si pour l'instant on a vraiment l'impression que c'est un nombre normal, ça n'a jamais pu être prouvé jusqu'à aujourd'hui.

Commentaire de Pingouin le 29/11/2004 21:49:15

Ouais la le coup du nombre "normal"...C'est quoi un nombre anormal ? Bref. Dites vous m'avez l'air calé : Ya pas un truc sur les décimales binaires qui a été démontré,  sur leur repartition notamment? Déjà il me semble qu'on peut calculer celle que l'on veut sans forcement connaitre les precedentes non ? (Mad motivé par un calcul de Pi ? développement en série de l'arctan ? ;-)

Commentaire de dnob700 le 29/11/2004 22:11:32

bien sur qu'un nombre normal c'est mathématique.

un nombre normal est un irationnel pour qui chaque chiffre à la même fréquence d'apparition (donc 1/10ème dans son dévelloppement décimal (la suite des ses chiffres)).

Un nmbre parfaitement normal, est un nombre normal dans toute les bases.

Et dire que Pi ne se répète jamais c'est dire qu'il est normal, ce qui n'est pas prouvé. C'est a dire que l'on sait qu'il n'est pas périodique (sinon il serait rationel) mais rien ne prouve que toute les suite de chiffre finissent par apparaitre à un moment ou un autre.

Commentaire de Mindiell le 29/11/2004 23:56:54

Le site de Gerard Villemin est une mine d'or d'ailleurs ;o)

Et dnob700, si PI ne se répète jamais, ca veut rien dire pour sa normalite. 0,01234657890123456789... est normal, mais pas irrationnel, non ?

Commentaire de vlad2i le 30/11/2004 18:12:32

Je confirme midiell :

1. racine de deux ne se répète pas, et pourtant il est bien irrationnel mais pas transcendant, or pi est irrationnel (d'après Ramanujan ca a été établi) donc il ne se répète jamais et la preuve expérimentale de son irrationnalité ne fait aucun doute - et transcendant .

Le seul doute est celui de sa transcendance, que l'on n'a jamais démontrée, mais qui semble se vérifier d'elle meme alors que l'on trouve de plus en plus de décimales.

Pour la question plus haut, il y a un algorithme qui permet de calculer une nième décimale binaire et qui a été utilisée pour calculer la 10^100 ème décimale binaire de pi (qui est un 1) mais est bcp plus lente pour calculer une décimale binaire et absolument innéficace pour calculer la série...

En ce qui concerne les nb premiers, il y a une probabilité d'apparence donnée (avec ln je crois) qui constitue la fonction zeta. En ce qui concerne pi, aucune probabilité possible (du fait de sa transcendance) et notemment a cause du 0 qui est plutot rare (surtt dans les 1000 premieres...)

Enfin bcp de problèmes quoi :)

Vlad

Commentaire de Pingouin le 01/12/2004 20:22:08

Personnellement j'ai hate de voir ce que tout ca va donner au final... (a part un centaine d'autres commentaires...)

Commentaire de sibi12 le 02/12/2004 18:27:40

Si tu multiplie après c'est inutile tu aura des chiffres mais qui n'ont aucune signification.
Si tu arrive à multiplier, moyennant quelque manipulation algebrique, au depart de l'algo la ça ira

Commentaire de scelw le 09/01/2005 14:53:13

J'aimerai savoir si le test de Miller-Rabin est plus rapide que celui des 3 indiens (en temps d'exécution sur ordinateur)... Quelqu'un saurait me répondre?

Deuxio, qui connait une bonne implémentation de l'algo des 3 indiens en VB ou C/C++ ?

Commentaire de scelw le 09/01/2005 16:10:41

salut! c'est cool si t'es motivé pour tenter d'implémenter l'algo des 3 indiens! je le suis aussi! on pourrait mettre en marche un projet de coopération... si tu as besoin d'aide pour certains symboles mathématiques, demande! sinon, tu veux coder l'algo en VB ou en C/C++? Je ne te cache que je préfère de loin le C/C++ au VB et que la supériorité du C/C++ en terme de rapidité est indéniable...

amicalement

scelw

Commentaire de dnob700 le 09/01/2005 17:21:05

en arithmétique, ce symbole est souvent utilisé pour la congruence, plutot que celui de l'égalité "normal"

Commentaire de dnob700 le 09/01/2005 17:56:11

non c'est le modulo

si en vb tu écrit :

x=a mod b
(en c tu mettrai x=a%b; )
en math tu l'écrit :
a=x modulo b (avec le signe égale à trois branche)
ou en abrégé :
a=x [b]   (avec le signe égale à trois branche)

c'est a dire que x est le reste de la division entière de a par b (attention, ce n'est pas forcement le plus petit reste).

il faut ausse remarquer que l'opération ne s'écrit pas dans le même ordre en math et en VB et que le signe égale spécial n'est pas obligatoire, on peut aussi bien écrire le signe normale.

Commentaire de sibi12 le 09/01/2005 18:11:40

Merci pour ces informations

dnob700 >>

"(attention, ce n'est pas forcement le plus petit reste)."

c'est à dire?

scelw >>

ok..je verrai  ca apres les examens. ^^

Commentaire de sibi12 le 09/01/2005 23:30:30

ah oui ok j'ai saisi. donc en fait si a=b [p] b n'est pas necessairement entre 0 et b-1. la relation est vraie pour autant que a=k*p+b avec k entier

Commentaire de Rman le 20/02/2005 01:06:14

juste pour dire si un jour tu te recentre sur le sujet, les nombre de mersenne sont bcp mais bcp trop previsible pour un codage de type RSA, meme si il sont tres grd. il nen reste pas moins que cest tres interressent :)
have fun pour la suite

Commentaire de BozzoDodo le 26/04/2005 11:23:29

Il y  a beaucoup de commentaires... je en sais pas si celui la a déjà été dit: il serait interessant de pouvoir cacher la fenetre, la mettre en icone à coté de l'heure par exemple, vu qu'on attend de ce programme qu'il travaille en arrière plan.
bonne prog'

Commentaire de MadM@tt le 26/04/2005 12:49:27

BozzoDodo >> Oui c'est exactement le problème de cette source, elle date un peu et j'ai toujours envisagé d'y mettre une gestion des grands nombres mais .... la flème héhé
enfin disons qu'on a tous des changements de projet des fois ;) mais si quelqu'un est motivé pour le faire je l'encourage !

Commentaire de Mindiell le 26/04/2005 14:01:57

Laisse tomber, arrête de re-re-re-re-re-inventer la roue, il existe des dizaines de libs qur le net qui gère les grands nombres sous formes de chaines de caractères ^^

Commentaire de ab44 le 25/08/2005 17:11:31

salut MadM@tt

C'est une source que je recherchait merci
mais j'ai un problème quand je clique sur ton exe, il y a message d'erreur qui dit:

"Erreur système &h80070583(-2147023485). La classe n'existe pas"

merci de m'aider

Bonne prog a tous.

Commentaire de MadM@tt le 25/08/2005 21:53:53

AB44 > le .manifest c'est le fichier qui sert à avoir l'apparence de windows XP (cherche sur vbfrance plein d'explications ;)
Pour la classe... aucune idée j'ai jamais utilisé de classe je n'ai pas commencé avec cette source, donc je ne sais pas du tout quoi de répondre désolé, essaye de recopier le code en copier collé sinon
A noter que j'ai fait ça sous VB5 c'est peut etre la le problème ??

Mindiell > lit la présentation de la source
Petit résumé : j'en avais envie, je m'ennuyai, ça me tentait etc etc etc... J'ai fait ça pour le plaisir et pour m'entrainer aussi, après bien sur tu peux me reprocher de l'avoir poster alors qu'il existe mieux et que je ré-ré-réinvente la roue ;) mais vu le nombre de commentaires, je pense que cette source a été interessante et le sera pour ceux qui cherchent des infos en venant ici
Voilà ;) bonne journée

Commentaire de Mindiell le 26/08/2005 10:27:03

Ben MadM@tt ! Je répondais à BozzoDodo et c'était au mois d'Avril :)
Ta source nous a tous intéressé puisque je participais depuis longtemps à la discussion ;)

Commentaire de the fake le 02/11/2005 14:46:33

Salut, deja bravo pour cette excellente source (j'aime pas laisser tourner mon pc sans rien quand je suis pas la ^^). je voulais juste te dire que l'on peut cinqtupler (* 5 ) la vitesse de recherche juste en désactivant la liste lors de la recherche, en sauvegardant seuleument quand l'utilisateur clique sur le bouton stop,en affichant pas le 1 er nombre de la liste lorsqu'il vide la liste, et en enlevant le manifest pour supprimer le thème xp, tiens le code (a peine modifié) :
Debut:
    Number = NombreEnCours
    ' cherche
    
    Liste.Visible = False
    
    Do
        If StopSearch = True Then GoTo Fin
        ' Afin de ne pas stocker trop de nombres dans la listbox on quitte et on revient
        If Number - NombreEnCours > 99999 Then
            NombreEnCours = Number
            
            Liste.Clear
            GoTo Debut
        End If
        If Premier(Number) Then Liste.AddItem Str(Number)
        Number = Number + 1#
        DoEvents
    Loop
Fin:
  Liste.Visible = True
    btnStop.Enabled = False
    Start.Enabled = True
    NombreEnCours = Number
    Save
    NumberStart.Text = Trim(Str(NombreEnCours))
    Me.Caption = "Fini !"
End Function

Voila je te donne mes résultats sur 20 seconde en partant de 1...
Original = 421010
Opti moyenne (sans thèmexp + liste invisible) = 1809972
Opti maximum = 2129262

Bon je sais que tu voulais pas enlever la fonction pour sauvegarder car si l'ordi plante.. m'enfin il va pas planter toutes les minutes quand meme !!!

A +

Commentaire de the fake le 15/01/2006 10:53:08

Salut !
J'ai refait le programme en C (c'est pas tout a fait le meme algo mais ca y ressemble) et les résultats sont vraiment flagrent !

Le programme me trouve 35 000 000 de nombres premiers en 10 sec...

Je vous poste le lien vers le progz ainsi que la source (je mt le tout dans un rar)..
Il existe des algo encore bien plus rapide, mais bien plus difficile a mettre en place, donc j'essaye pas trop :P

Au début le fichier enregistrait dans un fichier txt, mais d'une ca ralentissait, de 2 quand on arrive avec un fichier txt de 30 Mo en 3 sec, ca calme un peu..

Donc le programme vous dit juste le dernier nombre trouvé, si vous voulez quand meme que le log enregistre, dites le moi !

Ce n'est aps le meme genre de programme que celui ci, puisqu'on definit le nombre jusqu'ou il va chercher !

Assez blablaté, voici le lien :

http://bork0.free.fr/logs/premiers.rar

A+

Commentaire de the fake le 15/01/2006 20:30:37

Bon tout d'abord :
VEUILLEZ COMPLETEMENT IGNOREZ MON PRECEDENT CODE, JAI FAIT UNE FAUTE DANS LE CODE SOURCE.. BREF OUBLIEZ !

Par contre j'ai trouvé sur le net, un programme pour chercher les nombres entiers se basant sur le crible d'Ératostène (je sais aps si on dit comme ça) et accrochez vous bien...

Le programme me trouve 100 000 000 Millions de nombres 1ers en 15 sec, 10 Millions en 1 sec, 1 Milliards en 10 min..
J'ai refait les tests chez un pote avec un pc nettement plus performant (Amd athlon 3200 +, 1 Go de ram) et il trouve 2 Milliards de nombres premiers en 5 min...

Seuleument 3 pb :
-Il enregistre dans un txt, ce qui génère des txt de 2.10 Go (si si !)
- Les variables sont déclarés en unsigned long int cce qui fait des valeurs max de 4 295 000 000 (je sais plus exactement), et donc pas plus haut, il faudrait pouvoir les déclarer en long double, ce qui serait nettement mieux..

- Il faut lancer le log par l'invite de commande, mais ca je vous l'explique après !

tout d'abord telecharger le ici :
http://bork0.free.fr/logs/premiers.rar

et pour les linuxiens (ou mm les autres) la source ici :
http://bork0.free.fr/logs/premiers-sources.rar

Extractez (ou compilez) le .exe a la racine du disque (C:\), ensuite lancez l'invite de commande par demarrer - executer - cmd
puis faites des cd.. jusqu'a revenir a la racine (C:\) ensuite tapez votre commande sous cette syntaxe :

start Chercheprime.exe nombre_max (ou Chercheprime correspond au nom de l'exe)

Si vous voulez cherchez 1 000 000 000 de nombres, tapez :
start Chercheprime.exe 1000000000

Ensuite, une fenetre s'ouvre, bon et la... le log vous avertit quand c'est fini paar une méchante erreur !!

regardez dan sle répertoire oue s le log, vous devriez avoir primetab.txt, ouvrez le et tadam !
(si vous faites des recherches de 3 Milliards de nombres, n'essayez meme pas d'ouvrir le txt, il fera 3 Go :S )

Vous pouvez faire des test et comparez :

mon pc : Amd atlhlon 2000+ (fréquence a 1666 Mhz) - 256 Mo de ram me trouve 100 000 000 en 17 sec.. et 1 Milliards en 10-15 min

Pc d'un pote (3200 +, 1 Go de ram) : 2 Milliards de nombres en 5 min..

Voila, enjoy !

Commentaire de sibi12 le 15/01/2006 21:15:26

Ah oui aussi le .RAR ... C'est mal :-(

(Je deviens parano depuis que je suis sous linux :-( ... Mais ça se comprend ^^)

Commentaire de maestro1303 le 02/06/2007 22:41:04

Bonjour à tous,
Au risque de dire une bêtise je me permets de vous demander ceci:
Il y a un algo (très facile à mettre en place) du à sudaram(crible de Sundaram) qui donne tous les nombres impairs... non premiers! Ne serait il pas plus facile de stocker ces nombres dans une table ou dans un fichier et trouver alors les nombres impairs ne figurant pas dans cette liste qui sont alors -à coup sûr - tous premiers!

Commentaire de maestro1303 le 17/07/2007 20:19:52

Bonjour,

Est ce que quelqu'un peut répondre à mon message précédent?

Merci infiniment!

Commentaire de maestro1303 le 19/07/2007 20:30:27

Excusez moi de devoir vous faire cette requête un peu suagrenue.
Est ce que je peux faire tourner ce code sous Excel(vba)(Office2003).
Sinon Y aurit il un moyen d'avoir VB gratuitement.
Je crois aussi que l'idée de faire Sunduram ne doit pas être rapide sinon l'un d'entre vous l'aurait utilisée. donc j'abandonne ça.

Je ne vous dirais jamais assez combien je suis attaché à ce sujet.

Merci de votre compréhension et de vos réponses.
  

Commentaire de jmfmarques le 23/07/2007 11:28:37

Bonjour,  MadM@tt

Qui te parle de tester si le nombre est pair ?

Le 1er nombre premier est 2 ===>> tu l'inscris donc d'office.

Tu fais ensuite ta boucle d'ajout à partir de 3 et avec un step 2

Tu ne risques ainsi pas de balayer les pairs, non ?