Décomposition en nombres premier

     (déconseillée, pour cause de lenteur, avec Netscape pour des nombres de plus de 10 chiffres)

Entrez dans ce champ un entier de au plus 15 chiffres et lancez la décomposition en cliquant sur le bouton ...lancement de la décomposition!

  Le résultat va être affiché dans le champ ci-dessous ; par exemple si vous rentrez 9999999999 (10 chiffres 9) et dont la décomposition est 32×11×41×271×9091 vous allez obtenir 3^2*11^1*41^1*271^1*9091^1, avec a^b pour ab et u*v pour u×v.

Résultat :

Et bien entendu rien n'empêche de rentrer un autre nombre.

Ne pas hésiter à m'écrire en cas de problème (adresse sur la page d'accueil).

Quelques explications :

Pour des nombres de au plus 10 chiffres et avec un pentium 200 et IE4 la décomposition est quasi instantanée ( pour N4 c'est un peu moins rapide : parfois de l'ordre de la seconde, par exemple pour 216499999), du moins pour les nombres que j'ai essayés ... en 2001, date de la mise en ligne de cette page. Par contre si on dépasse 10 chiffres ca peut "mouliner " un peu si le nombre contient un grand nombre premier : par exemple pour 812345111111 (12 chiffres) IE donne la réponse (23×35319352657) en 2 à 3s et N en ....30s ; pour 812345111111123 (15 chiffres) IE donne la réponse en 4s et N en 50s et pour 812345111111129 (15 chiffres) IE donne la réponse en 40s (inutile de dire que je n'ai pas essayé avec N).
Par curiosité j'ai refais un essai en 2006 avec 240+15=1099511627791 (13 chiffres) qui est premier : IE sur mon pentium 200 met 12 secondes, alors que sur un pentium 740 de 2006 il ne met plus que 3 secondes.

Le fait que N soit si lent (12 à15 fois moins rapide que IE) doit être dû à une façon différente de travailler : avec IE lorsque le programme tourne on n'a plus la main et il ne doit pas y avoir d'échanges entre mémoire centrale et disque dur alors que c'est le contraire avec N.

Notons que IE, en cas de "pédalage", sort au bout de30s une première petite fenêtre qui offre la possibilité d'interrompre le calcul, mais la suivante n'apparaît qu'au bout de 3 mn ; quant à N il n'offre jamais la possibilité d'arrêter le calcul.

La décomposition est réalisée grâce à un petit programme en JavaScript mis dans le head de cette page html et qui s'exécute sur votre pc si.....vous n'avez pas désactivé JavaScript.

L'entier dont vous voulez la décomposition en nombres premiers doit être donné sous forme effective d'entier et pas sous forme d'une quelconque expression et il doit avoir au plus 15 chiffres, du moins sur mon pc où JavaScript encaisse l'entier 99...99 (15 fois le chiffres 9 ) et donne comme décomposition 33×31×37×41×271×2906161 ; avec 16 fois le chiffre 9 ce programme donnerait une décomposition manifestement fausse : 216×516, car il considère que le nombre rentré est 1016 (vrai à 1 près).

La méthode que j'utilise repose sur le fait que tout nombre premier supérieur ou égal à 5 est de la forme 6p+1 ou 6p+5 et donc le programme ne divise pas sytématiquement par tous les entiers impairs : il ne divise que par les entiers de la forme ci-dessus ce qui fait un gain de 33%.

Remarque 1 : je conseille à ceux ayant un besoin impérieux de déterminer la décomposition en facteurs premiers d'un nombre de plusieurs dizaines de chiffres d'aller faire un tour à http://www.alpertron.com.ar/ECM.HTM , ils ne seront pas déçus du voyage (en plus ils auront la décomposition en somme de 3 carrés ou 4 carrés).

Par exemple pour 99....99 (17 fois le chiffre 9) on obtient instantanément 32×2071723×5363222357

La méthode utilisée est en liaison avec les courbes elliptiques : inutile de dire que là, je passe la main....

Remarque 2 : rappelons que le succés de la méthode de cryptage RSA repose sur le fait qu'il est très difficile de décomposer, rapidement, en nombres premiers un nombre qui est le produit de 2 grands nombres premiers. Pour les professionnels, un grand nombre premier signifie un nombre de l'ordre 1080 ou 1090, cela d'après la revue APMEP n°434.

Remarque 3 : On appelle nombre de Mersenne (1588-1648) un nombre de la forme 2n-1, noté Mn

Ils ne sont pas tous 1ers (par exemple M4=15 n'est pas 1er).
En fait pour que Mn soit 1er, il est nécessaire que n le soit, puisque par application directe de l'identité an-bn=(a-b)(an-1+an-2b+...+abn-2+bn-1) on constate tout de suite que Mp×q est divisible par Mp et Mq ; par exemple M4=15 est divisible par M2=3.

Bien entendu, s'il est nécessaire que n soit 1er pour que Mn le soit, cette condition n'est pas suffisante :

Les nombres de Mersenne premiers battent régulièrement les records de primalité : voici une liste des plus grands nombres de Mersenne premiers connus (pour faciliter la lecture de grands entiers on sépare les tranches de trois chiffres par une virgule) :

date de la
découverte
valeur de
n
nombres de chiffres
de
Mn=2n-1
7/01/1674,207,28122,338,618
25/01/1357,885,16117,425,170
23/08/0843,112,60912,978,189
12/04/0942,643,80112,837,064
06/09/0837,156,66711,185,272
04/09/0632,582,6579,808,358
15/12/0530,402,4579,152,052
18/02/0525,964,9517,816,230
15/05/0424,036,5837,235,733
17/11/0320,996,0116,320,430

Oui, oui, ces nombres premiers sont constitués de plusieurs millions de chiffres : c'est dire la modestie de ce petit script.

Notons qu'il y a un lien étroit entre les nombres parfaits (entiers naturels égaux à la somme de leurs diviseurs propres) et les nombres de Mersenne premiers :

N est pair et parfait <=> N=2p-1(2p-1) avec 2p-1 premier

Le plus petit nombre parfait pair est 21(22-1)=6 (ses diviseurs propres sont 1, 2, 3 de somme 6).
27-1=127 étant premier, N=64×127=8128 est parfait.
Vérifions le.
Tous les diviseurs de N sont 1, 2, 4, 8, 16, 32, 64, et les mêmes multipliés par 127. La somme de ses diviseurs propres est donc (1+2+4+8+16+32+64)(1+127)-64×127=127×128-64×127=127×64.
Une conjoncture encore indémontrée est qu'il n'y a pas de nombres parfaits impairs!

Pour ceux s'intéressant aux grands nombres premiers et souhaitant plus de détails, voici trois liens : mathworld.wolfram.com/MersennePrime.html et www.mersenne.org et primes.utm.edu/largest.html

Enfin, je tiens à faire profiter le visiteur, qui aura eu la patience d'arriver jusque là, d'une de mes lectures : sur une découverte "récente" sur les nombres 1er.