A propos de nombres premiers

[Zorro]

@Zorro

Pour le cryptage RSA, je ne pense pas que ce sujet ait une utilité dans le domaine

c'est pourtant un fait !
le cryptage RSA se sert de nombres premier point a la ligne
tu peux grimper sur ton echelle ,comme ils disent par ici : " il va faire beau , les poules juchent "

note que je ne cite le cryptage RSA QUE pour montrer l'utilité des nombres premier (suite a question de Ar-s )

[fweil]

Bien ça, les propriétés des nombres permettant d'expliquer des aspects particuliers du comportement de la matière, oui. Et le comportement de la matière du microscosme jusqu'au macrocosme. Ce n'est pas le sujet, mais je confirme.

[PAPIPP]

Bonjour à tous

J’ignore si ce post pourra servir mais il offre une attaque des Nb premiers un peu différente.

J’avais en 2014 proposé un prg permettant la décomposition en Nb premier d’un Nb < 1e18
Pour diminuer le nombre de test j’avais utilisé la mise en matrice des nombres que l’on veut tester. Cette matrice devait avoir un maximum
de colonnes dans lesquelles ont ne peut avoir de Nb premier Il restait donc à tester les colonnes susceptibles de contenir des Nb premiers.

A titre d’exemple Voici le principe de mise en matrice des 1000 premiers nombres entiers naturels =>0

Si nous nous intéressons aux 2 3 5 7 11 13 etc. Nb premiers connus et que nous prenions leur produit comme modulo
nous pouvons créer une matrice des 1000 premiers nb naturels =>0 en prenant le reste de la division comme Numéro de colonne et la partie entière comme numéro de ligne.
Voyons les caractéristiques de cette matrice à travers le prg suivant.
Eviter dans un premier temps d’utiliser le produit de plus de 4 Nb premiers car on peut générer un vecteur de différences trop grand pour comprendre la récurrence.

Prenons comme exemple soit 2*3 ou 2*3*5
Avec 2*3=6 nous aurons une matrice de 6 colonnes et de 1000/6 lignes
Avec 2*3*5=30 nous aurons une matrice de 30 colonnes et de 1000/30 lignes
Le programme fonctionne pour des valeurs supérieures mais la lecture de la matrice sur la console ou sur papier n’est pas confortable

Cette technique de mise en matrice permet d’avoir une récurrence modulo le produit des premiers Nb premiers
avec un vecteur des différences entre les colonnes toujours identiques susceptibles de contenir des Nb premiers
car les colonnes contenant les Nb premiers sont toujours les mêmes seuls les lignes changent.

1) le premier avantage est la réduction des tests
A titre d’exemple prenons le modulo 2*3=6 il ne reste que 2 colonnes à tester ce qui nous fait une réduction de (6-2)/6=0,66 66 % de réduction
Et avec 2*3*5=30 il reste 8 colonnes à tester donc réduction (30-8)/30=0,73 donc 73% de réduction

2 ) le deuxième avantage est la récurrence ce qui permet de proposer des tranches de nombre à tester
exemple de 1 à 1e5 et de 1e5+1 à 1e10 et de 1e10+1 à 1e15 enfin de 1e15+1 à 1e18
D’autre part on peut passer d’un nombre premier à un autre nombre susceptible d’être premier d’une façon récurrente
avec le vecteur des différences entre les colonnes utiles.

3) le dernier avantage comme le vecteur des différences est récurrent il ne sera pas nécessaire
de continuer ni de constituer la matrice au-delà de la 2em ligne

Code : Tout sélectionner

;reste de la division d'un nombre X par le produit des n premiers nombres premiers  2*3*5*....*n=modulo
Dim T_MODULO.l(12)
Structure colonne
  NB.Q
  prem.a
  dif_prec.l
EndStructure

openconsole()
; **************** Réalisation du vecteur modulo à partir d'une table des nombres premiers des 100 premiers nombres *********
;***** Choix du premier Nb premier poue lequel le vecteur modulo sera appliqué.
;***** pour éviter la génération d'un vesteur trop important nous limiterons ce choix aux 11 premiers nombres premiers soit :2 3 5 7 11 13 17 19 23 29 31
;***** exemple Recherche du modulo < 2*3*5*7*11=2310 éléments du vecteur
SAISIE0:
mess$+"Filtre de réduction des diviseurs"
If Len(mess$)>120
  MessageRequester("Erreur","Colonne Div max  3 5 7 11 13 17 19 23 29 31"+#CR$+"Relancez le prg") ;
  End
EndIf
nb$=InputRequester(mess$,"Colonne Div max  3 5 7 11 13 17 19 23 29 31","5") ;
If Len(nb$)>Len("31")
EndIf
nbs=Val(nb$)
If nbs<3 Or nbs>31
  Goto SAISIE0
EndIf
Restore lab_pnbp
i=0
Modulo=1
Repeat
  Read.l ELEM
  If ELEM<>0
    T_modulo(I)=elem
    EL_modulo$+str(elem)+"*"
    Modulo*elem
    i+1
  EndIf
Until ELEM=0 Or ELEM=>nbs
el_modulo$=left(EL_modulo$,len(EL_modulo$)-1)
NBprem=i
nbs=ELEM
Dim tcol.colonne(modulo+2)
;*** Recherche des colonnes ayant des nb premiers   avec 2 colonne ne présente pas d'autre premier sur les lignes >1  ***
tcol(0)\prem=2
tcol(0)\NB=0
tcol(modulo)\prem=2
tcol(modulo)\NB=modulo

Tdep.q=ElapsedMilliseconds()
For inb=2 To modulo-1
  tcol(inb)\NB=inb
  For inbp=0 To nbprem-1
    If inb%t_modulo(inbp)=0
      tcol(inb)\prem=2
    EndIf
  Next
Next
;*** Recherche des colonnes ayant des nb premiers ***
cprec=0
for c=0 to modulo
  if tcol(c)\prem=2
    result$+rset(" ",4," ")+" "
    ;     res_dif$+rset(" ",2," ")+","
  else 
    ; ;     tcol(c)\dif_prec=cprec-c
    ;     tcol(c)\dif_prec=C-cprec
    result$+rset("P",4," ")+" "
    DERN_PREM_TROUV=C
    if PREM_NB_PREM_AV >0
      res_dif$+rset(str(C-Cprec),2," ")+","
      tcol(c)\dif_prec=C-cprec
      
    Else
      ;       res_dif$+rset(" ",2," ")+","
    endif
    if C>nbs and PREM_NB_PREM_AV =0
      PREM_NB_PREM_AV=c ;;; Recherche du premier nombre premier à partir duquel commence le cycle avec le vecteur des différences
                        ;       Cprec=C
    endif 
    Cprec=C
  endif
Next 
; comme la colonne 1 contient toujours des nombres premiers et que l'indice se trouve après modulo

tcol(modulo+1)\dif_prec=modulo+1-dern_prem_trouv
res_dif$+rset(str(tcol(modulo+1)\dif_prec),2," ")+","
tcol(modulo+2)\dif_prec=PREM_NB_PREM_AV-1
res_dif$+rset(str(PREM_NB_PREM_AV-1),2," ")+","


; debug  result$
printn (result$)
NBMAX=pow(2,10)
Lign=NBMAX/modulo+1 ;; limiter à 2^10 = 1024 suffisant pour la compréhension
col=modulo
; debug _n(lign)+_n(col)

dim tab.q(lign,col)
for i=0 to NBMAX
  lgn.l=i/modulo
  cln.l=i%modulo
  tab(lgn,cln)=i
next  
result$=""
for L=0 to lign
  ; for L=0 to 7
  for c=0 to modulo-1
    result$+rset(str(tab(L,c)),4," ")+" "
  Next 
  ;   debug  result$
  printn (result$)
  result$=""
next
Printn ("Le nombre à décomposer doit être supérieur au plus grand premier suivant qui forme le modulo produit des ="+el_modulo$+" ="+str(modulo))
Printn(" les colonnes qui ont une entête P sont les colonnes susceptibles de contenir des NB PREMIERS "+#CRLF$+" les autres ne peuvent en contenir")
printn( "le premier nombre à tester est "+str(PREM_NB_PREM_AV)+" dans la colonne "+str(PREM_NB_PREM_AV))
Printn( " Les NB PREMIERS pour lesquels les tests doivent être réalisés Sont les NB PREMIERS entête de colonne "+#CRLF$+" les autres tests sont inutiles")
printn(" Le vecteur récurrent des  différences entre les colonnes susceptibles de contenir des NB premiers"+#CRLF$+" ce qui permet de passer d'un nombre à l'autre est " +res_dif$)
Printn( "la somme des termes du vecteur   doit être égale à "+ str(modulo))
printn(" premier nombre à tester ="+str(PREM_NB_PREM_AV))
nb_prec_t=PREM_NB_PREM_AV
FOr ii=0 to 3
for ddd=PREM_NB_PREM_AV to modulo+2
  if   tcol(ddd)\dif_prec>1
    printn("Nombre suivant à tester "+ str(nb_prec_t)+"+"+str(tcol(ddd)\dif_prec)+"="+str(nb_prec_t+tcol(ddd)\dif_prec))
    nb_prec_t+tcol(ddd)\dif_prec
  endif
next
next
printn("*****  On peut continuer avec cette méthode récurrente comme cela jusqu'à la limite que l'on désire  ******")

printn("**** Taper sur une touche pour sortir *****")
input()  
CloseConsole()
end
DataSection
  lab_pnbp:
  Data.l 2,3,5,7,11,13,17,19,23,29,31,0
EndDataSection

A+

[PAPIPP]

Une petite info.
La nouvelle ne va peut-être pas bouleverser votre vie, mais elle est en train de faire sensation dans le monde
habituellement calme des mathématiques. Shinichi Mochizuki de l’université de Kyoto au Japon
affirme avoir démontré la «conjecture abc», un problème important de la théorie des nombres
proposé par David Masser et Joseph Oesterle en 1985 et qui porte sur le lien entre les nombres premiers
(2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37...), rapporte la revue scientifique Nature.

Pour sa démonstration, Mochizuki a développé des techniques que très peu d’autres mathématiciens comprennent complètement
et qui utilisent de nouveaux «objets» mathématiques. «A ce stade, il est probablement le seul à les connaitre tous» estime Goldfeld.
Et pour cause: la démonstration du Japonais est détaillée dans quatre articles scientifiques, qui reposent chacun sur d’autres longs articles. Brian Conrad de l’université de Stanford, explique:

Ici les 4 articles de Juillet 2016 à septembre 2016 en anglais.

http://www.kurims.kyoto-u.ac.jp/~motizu ... ry%20I.pdf

http://www.kurims.kyoto-u.ac.jp/~motizu ... y%20II.pdf

http://www.kurims.kyoto-u.ac.jp/~motizu ... %20III.pdf

http://www.kurims.kyoto-u.ac.jp/~motizu ... y%20IV.pdf

A+

[SPH]

Waouwww, je suis admiratif

[Ollivier]

@PAPIPP

Je pense que ton avant-dernier message est déjà établi dans le code de fweil page 1.

Le prochain code source sera un code tuto qui explique (concernant la recherche des premiers)

1) l'importance des p-factorielles en théorie
2) l'impossibilité de les utiliser de manière "brute" et "directe" en pratique,
3) leur nécessité pratique dans un réseau de calcul commun.

Il fera suite au 1er code source tuto.

Cela toujours dans le but de comprendre le code source de fweil.

Pour les liens que tu as mis vers les PDFs du japonais, je pense que je pourrai faire une code source pédagogique à ce sujet dans une dizaine de milliers de siècles!

Tu y as compris quelque chose? Pour ma part, je suis dans l'impossibilité de les télécharger...

[Ollivier]

@fweil

En espérant que le principe de cribler N * N comme premier crible de chaque nombre premier N soit mathématiquement viable, le carré de N n'est pas le seul saut "faisable".

Pour chaque nombre premier N "observé" (d'où mon insistance bête et méchante à maintenir la condition "If Multiple(N) = 0" en pensant qu'avant de cribler, Erathostène "regardait" son crible... Au cas où-!-) :

1) On cherche Na le nombre premier précédent
2) S'il n'y en a pas (avec : N = 2), Na = 1
3) On calcule L0, la p-Factorielle de Na
4) Rappel : p-Fact(1) = 1
5) On commence la "quête" et "enquête" avec x = 0 : chaque nombre récupéré sera Q0, Q1, ..., Qx.
N0 = N
5a) On prend N1, le Nb1er suivant notre Nb1er N0.
5b) On calcule Qx = N1 - N0 (gap)
5c) On calcule Sq la somme des Qx
5d) Sq > L0 ?
5e) Oui, on quitte l'étape 5, le tableau aligné Q(x) contient les valeurs prêtes à être traitées avec les AVX
5f) Non, on translate N0 = N1...
5g) ... Et on retourne à l'étape "5a"
6) Transfert AVX ("load")
7) Multiplication AVX des gaps Q(x) par N
Criblage


La p-Factorielle générale étant un dangereux goufre à ressources, autant pré-calculer la séquence de 7 avec ses 8 gaps :
4, 2, 4, 2, 4, 6, 2, 6
Comparativement, il me semble que tu faisais :
2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2
Donc le gain possible avec AVX serait :
1, 0, 1, 0, 1, 2, 0, 2 somme = 7 sauts de gagnés sur 15 (un peu moins de 50% de gains pour 2 registres YMMn utilisés).

Application du protocole ci-dessus avec 7

1) On cherche Na le nombre premier précédent
Na = 5
3) On calcule L0, la p-Factorielle de Na
L0 = p-Fact(5) = 5 * 3 * 2
L0 = 30
5) On commence la "quête" et "enquête" avec x = 0 : chaque nombre récupéré sera Q0, Q1, ..., Qx.
N0 = N
N0 = 7
5a) On prend N1, le Nb1er suivant notre Nb1er N0.
N1 = 11
5b) On calcule Qx = N1 - N0 (gap)
Q(0) = 11 - 7
Q(0) = 4
5c) On calcule Sq la somme des Qx
Sq = Q(0)
Sq = 4
5d) Sq = > L0 ?
4 > 30 ?
5f) Non, on translate N0 = N1...
N0 = 11

rebelote...

5a) On prend N1, le Nb1er suivant notre Nb1er N0.
N1 = 13
5b) On calcule Qx = N1 - N0 (gap)
Q(1) = 13 - 11
Q(1) = 2
5c) On calcule Sq la somme des Qx
Sq = Q(0) + Q(1)
Sq = 4 + 2
Sq = 6
5d) Sq= > L0 ?
6 > 30 ?
5f) Non, on translate N0 = N1...
N0 = 13

rebelote...

N1 = 17
Q(2) = 17 - 13 = 4
Sq = Q(0) + Q(1) + Q(2)
Sq = 4 + 2 + 4

rebolote...
(j'abrège)
Sq = 4 +2+4+2+4+6+2+6
Sq = 30
On quitte la boucle avec notre séquence Q(x)

6) Transfert AVX

Code : Tout sélectionner

4   2   4   2   4   6   2   6
*
7   7   7   7   7   7   7   7
=
28  14  28  14  28  42  14  42
+                                         (+ N * N)
49  49  49  49  49  49  49  49
=
77  63  77  63  77  91  63  91
Ça c'est notre crible donc transfert pour l'avancement de la cible dans le crible.

On fait pareil avec les autre 1ers jusqu'à "plus soif".

Ex avec 11

Code : Tout sélectionner

4   2   4   2   4   6   2   6
*
11  11  11  11  11  11  11  11
=
44  22  44  22  44  66  22  66
+                                         (+ N * N)
121 121 121 121 121 121 121 121
=
165 143 165 143 165 187 143 187

[Ollivier]

Bon, ben avec le crible d'Erathos. que j'ai assorti de quelques calculs j'atteinds le nombre 1er "134 217 689" et tous ses prédécesseurs en moins de 3 secondes et demi, sans optimisation ASM, sans multi-thread, sans AVX et en 32 bits seulement.

Cependant, je souhaite tester la méthode "classique" moins gourmande en mémoire (20 fois moins de mémoire) mais plus lente (à ce stade, c'est 1000 fois plus lent, mais bon...).

Parce que là le 32 bits, il veut plu, il m'a dit que mes tableaux de 1 giga, je peux me les mettre dans un accès mémoire invalide bien inconfortable.

[Edit]J'ai débogué l'IMA, et là je peux dire que j'ai atteind les limites du 32bits "cool"
1 073 741 741
1 073 741 783 et
1 073 741 789 sont respectivement les
54 400 026 ième,
54 400 027 ième et
54 400 028 ième nombres premiers en natif PureBasic en moins de 12 secondes (aucune optimisation précitée).

[djes]

Pour les benchmarks, je me suis amusé à coder un petit programme de recherche, pas du tout optimisé mais 64 bits, et pour aller jusqu'à 10^9, le programme de fweil met 7 secondes, et le mien ... 155 secondes !

Battu par KO, je vais me coucher

[fweil]

Mes temps sont sans debug ... tu es sûr de pas l'avoir laissé ?

[djes]

Pour le tien ou pour le mien ?

Je vais essayer d'optimiser un peu pour le fun.

[Ollivier]

@fweil

Ce serait intéressant que Djes compare aussi l'algo à base d'Erathos que je t'ai montré.

Concernant tes deux questions, les réponses sont simples :

1) Le départ de la séquence, c'est N au carré.

2) Sa taille (ainsi que sa nature) ou période se définit comme indiqué dans le protocole plus haut (mon message d'avant le précédent)

Aussi, je n'ai pas compris ce que signifie 500M : 500 millions ou 500 milliards par seconde ?

[fweil]

500 millions avec M comme méga.

[djes]

@fweil

Ce serait intéressant que Djes compare aussi l'algo à base d'Erathos que je t'ai montré.

Moi je veux bien mais j'ai déjà plusieurs algos perso en tête, si j'en incorpore d'autres, j'explose ! Mais si tu mets le résultat pour 10E9 chez toi avec le prog de fweil, et ensuite avec le tien, on peut comparer...
Sinon je veux bien filer mon code mais je voudrais d'abord le finir...

[Ollivier]

@Djes

Je comprends ta difficulté. J'ai sorti une réflexion semblable à fweil : c'est parfois, au moins temporairement, plus constructif de ne pas avoir une totale idée des autres algos pour laisser son imagination chercher correctement.

Je me rends compte aussi que PAPIPP et moi avons une optimisation mathématique qui me semble finalement ne pas être dans l'algo de fweil, ce qui est hautement prometteur, car je sais comment le faire évoluer à un stade non "manuel".

J'estime être 12 fois plus lent que fweil, mais c'est à un stade qui n'est pas encore limité en calcul, ni optimisé.

Je pense que lorsque nous aurons réussi à atteindre ou légèrement dépasser l'algo de fweil, il faudra enfin réunir nos idées, ce qui ne sera pas une mince affaire ! Est-ce que l'OVNI que j'ai reçu de ta part a un rapport avec ton algo ?