Attention, TROUVAILLE :
Pour savoir si N (>3) est premier,
il suffit (apparement) que :
3(N-1)-1 Mod N = 0
J'en suis arrivé a cette formule en analysant profondement mon test de primalité que je vous avais livré il y a quelques mois dans ma "conjoncture magnifique de SPH" !
En simplifiant :
N est premier si :
2(N-1)-1 Mod N = 0
Ce qui permet de trouver tres facilement si un mersenne est premier ou non.
Cela se traduit comme ceci :
La representation binaire d'un Mersenne M(X) de l'expression 2(X-1)-1 s'écrira avec X-1 "1" auquel on applique un Modulo X
Exemple : pour savoir si M(5) est premier, On fera 1111bin Mod(5)
J'attend de voir si qqun peux calculer M(M(127))
Oops, vous m'aviez compris :Envoyé par SPH
pour savoir si 31 (c'est a dire M(5)) est premier,
On fera 111111111111111111111111111111 Bin Mod(31)
Dernière modification par SPH ; 30/12/2005 à 07h51.
Desolé cela ne marche pas pour certain nombres :
Prenons n=561
On a bien
Et pourtant 561 n'est pas premier (561=3*11*17)
Fait une recherche sur les nombres de Carmichael (http://fr.wikipedia.org/wiki/Nombre_de_Carmicha%C3%ABl par exemple)
Alors la, je suis tres déçu...Desolé cela ne marche pas pour certain nombres :
Prenons n=561
On a bien
Et pourtant 561 n'est pas premier (561=3*11*17)
Fait une recherche sur les nombres de Carmichael (http://fr.wikipedia.org/wiki/Nombre_de_Carmicha%C3%ABl par exemple)
J'utilise la calcul de windows donc, je ne peux pas verifier pour 561 mais si
(2^560)-1 Mod 561=0
alors, il y a une exception qui m'est passé entre les doigts...
ps : Et avec 3^(N-1)-1 Mod N ??
ps2 : ma formule ne marcherait elle pas pour 100% des mersennes premiers ??
Dernière modification par SPH ; 30/12/2005 à 10h04.
Il suffit de prendre 1105 (=5*13*17) comme contre exemple.Et avec 3^(N-1)-1 Mod N ??
Tout les nombres premiers vérifient tes deux formules, mais hélas certains nombres non premier la vérifie égalemmentps2 : ma formule ne marcherait elle pas pour 100% des mersennes premiers ??
J'ai retenu cela des nombres de carmichaël :
Plus les nombres deviennent grands et plus les nombres de Carmichaël deviennent rares.
Puisque j'ai trouvé cette formule dans le but de calculer la primalité d'un mersenne, la vrai question est d'abord celle ci :
2 puissance un nombre mersenne style M(35 million) est il calculable et stockable ??
Si oui, alors mon test prend tout son sens car en quelques heures, on pourra calculer si
2CE MERSENNE -1-1 Mod CE MERSENNE = 0
En effet, il suffit d'une seule operation. Et pour eviter de tomber sur un nombre de carmichaël, on peux faire un autre test deterministe.
En tout cas, cette seule operation remplace des millions d'operation qui durent un mois !! Quel gain de temps !!!!!!!!
marche pas pour 91 121 etc
et evidament on peut pas calculer 2un nombre de mersenne
faudra 101000000000000000000000000.... memoire
et on a que 109
Dernière modification par deep_turtle ; 02/01/2006 à 07h46.
Bon, je vais me replonger dans mes formules pour essayer de simplifier...
Non : élever à la puissance un nombre de Mersenne de 10^6 chifffres est plus long que le test de Lucas-Lehmer.
Il y a 1 muliplication et 1 modulo pour chaque itération. Pour la puissance, il faut 1 multiplication et 1 modulo si il y a un 0 dans le bon bit et 2 multipications et 2 modulos si il y a un 1 dans le bon bit.
Pour les nombres de Mersenne, on peut calculer
2^(2^n) et en déduire le résultat de 2^(Mn-1).Tout ça modulo Mn.
Dans ce cas il y a 1 un à la fin et que des zéros. On peut donc se contenter de faire n élévations au carrés et n modulos.
Conclusion : on arrive à la même complexité que le test de Lucas-Lehmer mais le résultat, s'il est premier est peut-être faux.
Il y a plus de nombres pseudo-premiers en base 2 que de nombres de Carmichaël et c'est ceux là qui nous intéressent.
Bonne année, peut-être commencé par des calculs sur les nombres de Mersenne.
SPH,
Plutôt qu'utiliser des outils de Windows, télécharge PARI/gp. Il y a un exécutable pour Windows. C'est TRèS pratique !
Quant à ce que tu viens de trouver, c'est le petit théorème de Fermat si je ne m'abuse !? (quoique, avec ce que j'ai bu pour le Nouvel An, je n'ai pas l'esprit très clair).
Il me semble aussi me souvenir qu'il y a des conjectures pour les nombres de Mersenne et Fermat : Si, alors N (mersenne ou fermat) est premier. Mais pas de preuve ... Et puis, on ne fait pas de maths à 3 heures du mat ...
En tout cas, utilise PARI/gp, c'est SUPER !
Allez, 2006 c'est parti !
Tony
Théorème de Fermat :
pour tout nombre premier p et pour tout a: a^p=a mod p.
Une variante avec a premier avec p : a^(p-1)=1 mod p.
Bon nouvel an!
Et bin, je suis épaté. Ca ne vous épate pas que mes recherches débouche sur le petit theoreme de fermat sans que je le sache ?? Ca m'encourage....
Continue !!
Amateur moi aussi, je me suis vite rendu compte que l'expérimentation apporte souvent plus de questions que de réponses ... Il te faut aussi vite développer ta connaissance des méthodes et théorèmes de base de Théorie des Nombres. Certaines choses surprenantes du point de vue de l'expérimentation deviennent souvent assez banale quand on utilise les outils théoriques pour les prouver. Mais surtout, un phénomène vrai 1 milliard de milliards de fois peut être faux à l'essai suivant (exemple donné dans le livre suivant !). Toute découverte Mathématique doit être prouvée rigoureusement pour être acceptée ! (Parfois, c'est vrai, il est impossible de trouver une preuve (Golback, ...), mais c'est rare !).
Je te recommande le livre de JP Delahaye sur les Nombres Premiers (Belin, je crois)? En français ! Un très bon moyen pour commencer !
Il y a un manque de livre de Théorie des Nombre en Français ...
Tony
Je confirme : édition "Belin Pour la science".
Je recommande aussi tous les livres qu'il a écrit (J'en ai lu quelques un).
Le titre est "Merveilleux nombres premiers".
Mais pour savoir quelque chose de précis (comme pour les nombres de Mersenne et de Fermat) mieux vaut internet : JP Delahaye ne peut écrire tout les sujets, et décrire les méthodes,... car le livre ferait énormément de pages.
Même sur internet, il y a pas beaucoup de chose en français.
A+.
3 livres :
Théorie des Nombres et Cryptographie
An Explicit Approach to Elementary Number Theory
Hardy: Introduction à la théorie des nombres
Le premier, en Français, contient quelques pages intéressantes.
Le 2ème, bien qu'en Anglais, est très bien. En plus, il prend des exemples en PARI/gp. (Voir 7.2 : Calcul de puissance avec modulo !)
Quant au dernier, cela fait presqu'un an qu'ils promettent sa sortie ! Encore au moins 1 an à attendre !
Tony
Sinon il y a aussi des cours d'algèbre accessibles dans la bibliothèque de mathématique. Ca peut être un bon départ
Oui, certainement. Mais l'approche est différente de ce qui se fait aux US, il me semble. TonySinon il y a aussi des cours d'algèbre accessibles dans la bibliothèque de mathématique. Ca peut être un bon départ
Toutes les approches sont bonnes, et l'étude théorique des structures algébriques peut être passionante
Re : >>> Test de primalité en 1 opération :
Je recommande "les maths en tête- Algèbre" de X. Gourdon, le début est intéressant: un cours niveau bac+1, 13 exercices avec des développements suggérés parfois, 4 problèmes d'arithmétique (corrigés): Cryptographie (le système de chiffrement RSA)
Nombres pseudo-premiers et nombres de Carmichaël
Quelques test de primalité
Quelques cas particuliers du théorème de Dirichlet
et 4 sujets d'étude corrigés: Théorème de Tchébycheff
Symbole de Legendre et applications
Sur les entiers somme de deux carrés
Tout entier est somme de quatre carrés
De quoi acquérir de bonnes bases...
"Plus les choses changent et plus elles restent les mêmes..." Snake Plisskein
