Test de primalité sans algorithme

[fabientoulgoat]

Bonjour, je propose un test de primalité sans algorithme:

http://www.cjoint.com/doc/16_12/FLtojAa ... 150018.jpg
http://www.cjoint.com/doc/16_12/FLtojdh ... 150042.jpg

On peut définir la primalité d'un nombre en posant:
f(x,y)=g(x,y)=h(x,y)=le plan Oij

Pour 23 aucune section ne croise un nombre entier
car 23 est premier
Pour 24 beaucoup de sections croisent un nombre entier
car 24 =2*2*2*3

Les fonctions sont peut être erronées mais l'idée est là...
Merci!

PS:
- h(x) est égale à 0 aux valeurs entières de (x)
- erreur sur le dessin:
- g(x,y)=sin((pi(23-x))/y)
- "le plan régi par (z)" comprendre "le plan Oij

[fabientoulgoat]

Pour explication, j'ai reproduit ce dessin avec f(x,y) par exemple
les droites sont formées par les multiples des nombres
à gauche les nombres, à droite leurs multiples successifs

Code: Tout sélectionner

01  02  03  04  05  06  07  08  09  10  11  12  13  14  15  16  17  18  19  20  21
    02      04      06      08      10      12      14      16      18      20
        03          06          09          12          15          18          21
            04              08              12              16              20
                05                  10                  15                  20
                    06                      12                      18
                        07                          14                          21
                            08                              16         
                                09                                  18       
                                   10                                       20

[nodgim]

Est ce que tu te rends compte de la taille (ou de la précision) que devrait avoir un tel graphique pour des nombres à 1000 chiffres ? (On en est à peu près à cette taille pour les codes RSA) ?

Ce n'est tout simplement pas réalisable.

NB: dans le même ordre d'idée, tu pourrais tracer la fonction y = A/x, A étant le nombre à factoriser. Le croisement de la courbe avec un point à coordonnées entières fournit un élément de la factorisation.
Là encore, c'est en pratique irréalisable.

[Ben314]

Salut,
Perso, surtout, je ne vois pas vraiment où réside la différence entre ton truc et le fait de tester on ne peut plus bêtement "est-ce divisible par 2 ?" "est-ce divisible par 3 ?", etc...

Parce qu'il faudrait peut être comprendre qu'entre écrire "a divise b" et sin(pi.b/a)=0, c'est effectivement équivalent, mais il y a une "petite différence" : l'un se fait rapidement (que ce soit de tête ou avec un ordi.) et l'autre... pas vraiment...

[Pseuda]

Bonsoir,

C'est ce qu'on appelle le crible d'Erathostène.

[fabientoulgoat]

...
Merci pour vos réponses
Je pensais avoir trouvé quelque chose

[WillyCagnes]

bsr,
connais tu la Spirale d'ULAM?
https://fr.wikipedia.org/wiki/Spirale_d'Ulam

http://villemin.gerard.free.fr/Wwwgvmm/Premier/Ulam.htm

et ceci
http://falun-fr.blogspot.fr/2016/11/sci ... rs_12.html
http://www.les-mathematiques.net/phorum ... 313,860664

[danyL]

"les nombres premiers sont multiples de 6 plus ou moins 1"
je ne connaissais pas cette propriété étonnante, les nombres premiers étant réputés rebelles à l'ordre

qq sait si elle a servi à démontrer, trouver d'autres propriétés des nombres premiers, en travaillant en base 6 comme le suggère le gars de www.les-mathematiques.net ?

[anthony_unac]

Bonsoir,
Définir un "test de primalité sans algorithme" c'est assez étrange car un algorithme en général est une suite d'instructions "genre fais ci, fais ça" n'est ce pas ce que l'on fait subir à un entier donné pour tester sa primalité ?
Pour le dire autrement, définir un test de ^primalité sans algorithme ce serait comme "chercher la fumée sans feu ".
Pour le reste, je connais un crible (autre que celui d'Eratosthène) qui concerne les nombres premiers et qui ressemble plus ou moins à vos travaux.

[nodgim]

Dire que les nombres premiers sont de la forme 6k + 1 ou 6k-1 (sauf 2 et 3) provient uniquement du filtre des multiples de 2 et 3 : de la séquence des 6 nombres consécutifs 456789 ne reste que 5 et 7.
Tu pourrais filtrer le 5 aussi, donc dans une séquence de longueur 2*3*5= 30, et déterminer les non multiples de 2 3 ou 5. Mais cette méthode a ses limites, surtout par la longueur de la séquence qui croît exponentiellement.