nombres premiers : limites des technologies actuelles

Voir le sujet précédent Voir le sujet suivant Aller en bas

nombres premiers : limites des technologies actuelles

Message par Admin le Mar 24 Sep 2013 - 10:33

Nombres Premiers (NP) et limitations des technologies actuelles 2013 xads


Ecrire et faire "tourner" suffisamment longtemps des programmes informatiques qui voudraient :
- Démontrer la conjecture forte de Goldbach (échec)
- Tenter de trouver un nombre Premier de UN milliard de chiffres (échec)
posent quelques soucis de stockages et de représentations.

J'ai exclu le nombre  2 de l'ensemble des NP et dès lors je considère que tout NP est nombre Impair.

Par la suite, je vais appeler NxF le nombre de chiffres (longueur)  d'un nombre.
Ainsi 97 aura un NxF=2  et 95111 un NxF=5.  
Il est évident que la différence entre un NxF de 4 et de 3, est une puissance de 10 en plus.
Il en va de même entre un nombre de NxF de un million et un nombre de NxF  de (un million + 1)  
sauf que cette puissance de 10 en plus, porte déjà sur un nombre gigantesque !

Le  tableau ci-dessous [corriger] , donne une idée sur le nombre d'impairs que l'on peut rencontrer selon la longueur des nombres.  Ex: combien d'impairs possibles pour un nombre de 3 chiffres ? (=450) .  
 
NxFNombre min
Pour ce NxF
Nombre maxQuantité de nombres avec ce NxFQuantité de nombres IMPAIRS avec ce NxF
2101 = 10102 -1 = 999*101 = 90
3102103 -1 = 9999*102 = 900(900/2)=450
4103 = 1.000104-1 = 9.9999*103 = 9.000(9000/2)
9108=100.000.000109 -19*108-1(9*108) / 2
10109=1.000.000.0001010 -19*1010-1(9*109) / 2
10010(100)-1=109910100 -19*10100-1
100010(1000)-1=109999*10999
106 (1 million10(10**6) -19*10999.999
107 (10 millions10(10**7) -11010**7 -19*10(10**7)-1(9*109.999.999) / 2
108 (100 millions10(10**Cool -11010**8 -19*10(10**Cool-1(9*1099.999.999) / 2
109 (1 milliard10(10**9) -11010**9 -19*10999.999.999(9*10999.999.999) / 2
Passer d'un nombre de 10.000.000 de chiffres à un nombre de 17.425.170 chiffres
implique une puissance supplémentaire de 10**7.425.170 ,  et c'est affolant.

Il est  vrai que plus on avance dans des nombres avec  des  NxF  importants  
plus les  Impairs  ont des chances de se trouver être un multiple d'un Premier déjà rencontré.
déjà, éliminer  tous  les impairs multiples de 3, de 5, 7, 11, 13, 17  ..
Mais aussi,  plus on avance dans des nombres avec des  NxF  importants ,
plus on va rencontrer des quantités d'impairs importantes !

A moins qu'au-delà d'un certain Impair de taille titanesque, il n'existe plus de nouveau Premier !
Autrement dit l'ensemble des Premiers serait borné. [le contraire a été démontré]  
L'idée que, la conjugaison des multiples des Premiers déjà rencontrés pour tout Impair supérieur à une valeur titanesque, borne l'ensemble des Premiers, est intéressante en soi, mais cela s'arrête là.

"La théorie"  des nombres Premiers, c'est aussi la théorie de la conjugaison des multiples des Premiers
déjà rencontrés dans un ensemble d' impairs*  de taille colossale.  

Si je savais décrire cette conjugaison de façon certaine, j'aurais fait un grand pas pour l'humanité [rire] .

Mais là n'est pas mon propos.

(*) ou pas


"Table" des NP  (TNP)

Table des NP  (TNP)

Je voudrais rappeler que la seule écriture d'un nombre de 10 millions de chiffres va occuper une "surface"
d'environ  5 millions d'octets (5 Mo)  [avec compression].
Et  il y a près de  4.5 fois 10 puissance 10 millions d' Impairs, dans ce cas, candidats à être Premier (ou pas) !

C'est l'objet  de la TNP : on essaie de stocker le minimum de Premiers  (dont ceux de très grande taille)
on se concentre plutôt sur les distances entre eux.

Exemple : voici à quoi pourrait ressembler la TNP avec  des NP  très, très  petits :  ici  de NxF=5
994018 9940932 994318 9943930 9946918 9948710 9949126 995234 995272 99529
995518 995594 995638 995716 995774 9958126 996074 9961112 9962320 99643
[br]La distance entre 99551 et 99559 est de 8.  J'utilise ici une distance "relative". [corriger]  
Chaque ligne étant identifiée par un  "Premier de base". Chaque ligne est une "tranche" de Premiers.

Je ne suis pas dans la précision absolue de l'arithmétique :
les grandeurs que  j'évoque ici,  se contentent souvent d'approximation, c'est suffisant pour ce que je veux en faire.  

Je suis quand même obligé –de temps en temps- de stocker un Premier de Base sur "disque" pour alléger les calculs.  Ainsi lorsque j'ai épuisé le parcours de la Tranche des "99401" il faut que je récupère celle des "99551"
(ce n'est qu'un exemple trivial, la réalité est bien plus complexe) .

Il  me semble qu'un record (paquet de bytes sur disque) ne peut dépasser 2.147.483.647 bytes (2Go) ,
dans le meilleur des cas,  avec le langage "Pascal".[corriger]  
Pour une Tranche, j'ai tout intérêt à aligner la taille de mes records à leur plus grande capacité possible : 2Go.

Je vais tenter de rechercher le Premier de Base  par un "indice" (référence à la position de cette tranche dans la TNP donc  aussi sur "disque")  et qui va me servir à retrouver les distances implémentées pour lui.
Cet "indice" va me permettre de retrouver la 1ére Tranche, la seconde, etc..

Avec le langage "Pascal" cet "indice" ne doit pas excéder [corriger]  la taille d'un LongWord donc  4.294.967.295 d'indices :  c'est dire que je ne peux pas "adresser" plus de  4.294.967.295  de  Tranches,
à moins de complexifier fortement le système d'adressage.

Maintenant, dans  UNE  "Tranche" combien pourrais-je stocker de "distances" (donc de Premiers) ?
Une  distance,  sera représentée par  un  4 bytes.  Ainsi avec un  LongWord  la plus grande distance
que l'on peut stocker est 4.294.967.295  ce qui semble énorme.
Mais n'existe-t-il pas un Premier P1 et son successeur P2 tels que P2 moins P1  >  4.294.967.295  ?
C'est plus que probable, c'est même certain.  Et ces premiers ont quels NxF ?
On va atteindre là, la limite de notre spécification informatique de la distance.
Notez que si je présente la distance avec un 8 bytes au lieu de 4, j'ai toujours  la certitude de dépasser un jour, sa capacité !  Mais de quel NxF ?

Pour un "Premier de Base", dans la TNP, il est nécessaire de stocker le maximum possible de distances
dans sa Tranche de  2 Go (LongInt)  [corriger].  
Autrement dit, tout accès disque ne pourra pas restituer/stocker plus de 2Go  par record. [corriger]  
Et sur ces 2Go  en théorie  je pourrais  stocker  ½  milliard  de distances, environ.
Est-ce à dire qu'il faut stocker comme "Premier de Base", UN Premier tous les UN demi  milliard  de Premiers environ ?

Dans ma "Table" TNP  je ne peux donc  stocker/retrouver  que  4.294.967.295  Tranches  avec mon indice,
qui  chacune  stocke  0.5 milliard de distances avec ses Premiers successeurs de sa Tranche.    
Je peux donc stocker en tout un peu plus de 2*10**18  distances donc de Premiers environ.

Il faut voir que dans les nombres de NxF=10**7 chiffres  il y a  [ (9*10**9.999.999) / 2]  nombres Impairs de  10**7  chiffres  [corriger]  mais combien de Premiers  ?


Si  je  décrète  que dans les impairs de NxF=10**7 chiffres  il y a "seulement"  5%  de nombres Premiers
cela  me donne  5%  de [ (9*10**9.999.999) / 2]  soit environ 2*10**1.000.000  de Premiers de NxF=10**7 à découvrir. [corriger]  

Comparé aux 2 * 10**18 (environ)  Premiers "stockables" avec la technologie,
Ces 2*10**1.000.000  de Premiers de  NxF=10**7  -et même s'ils sont 2 fois moins nombreux-
sont  déjà infiniment plus nombreux  que ce que peut supporter cette  technologie !  

La taille d'un record,  la taille de mon "indice", la taille d'une Tranche, la taille d'une "distance", ..  
ne sont pas spécialement adaptées à cette recherche via  l'informatique, à ce jour.

Sans compter qu'il faut que j'arrive à stocker sur mes "disques"  les quantités astronomiques
de bytes  que cela représente, et que je n'explicite pas ici.


Technologies
Pourquoi  le langage "Pascal"   plutôt que C, ou tout autre ?  Pourquoi  Intel plutôt que Z/os ?
Si  l'on veut travailler avec des nombres de 10**7 chiffres ou plus,  finalement ils sont presque tous équivalents
quand à leurs capacités d'adressage et de stockage.
La technologie "binaire" (d'où découle le byte) n'est pas adaptée.
La taille de la mémoire, l'architecture,  les supports externes (disques) non plus.


Les nombres de NxF  >= 10 millions de chiffres sont inaccessibles avec les technologies actuelles.
Et pour trouver les  2*10**1.000.000  de Premiers de  NxF=10**7  (et même s'ils sont 2 fois moins nombreux)  
il faudrait que je complexifie fortement le système d'adressage
et que je trouve  quelques  téraoctets pour les disques  et  la mémoire .


L'informatique distribuée en réseau me semble efficace, que si et seulement si, on se pose comme question :
"le nombre (n)  est-il premier ?". [corriger]  


Il y a des limites où  "ruser" devient impossible.
Là où on voudrait tenter de jouer dans la cour des Dieux, on n'y arrive pas (encore).


Il faut abandonner la recherche des nombres Premiers  (par cette méthode)
ou alors s'arrêter aux possibilités des technologies actuelles.

Admin
Admin

Messages : 7
Date d'inscription : 20/06/2013

Voir le profil de l'utilisateur http://seguiere.forumactif.org

Revenir en haut Aller en bas

Re: nombres premiers : limites des technologies actuelles

Message par zaduk le Sam 19 Oct 2013 - 15:31

j'en ai mal à la tête

zaduk
Invité


Revenir en haut Aller en bas

Voir le sujet précédent Voir le sujet suivant Revenir en haut

- Sujets similaires

 
Permission de ce forum:
Vous ne pouvez pas répondre aux sujets dans ce forum