Nombre premiers

Un problème, une question, un nouveau théorème ?

Messages : 790

Enregistré le : 23 oct. 2008 23:49

Re: Nombre premiers

Message par Dadin » 15 févr. 2011 20:25

J'ai peut-être pas été convainquant vu que c'étaient de petits nombres, mais par exemple le calcul de
PGCD(348009867102283695483970451047593424831012817350385456889559637548278410717,445647744903640741533241125787086176005442536297766153493419724532460296199) devient immédiat.

Valvino : lolwut !

Messages : 2382

Enregistré le : 22 juil. 2008 02:29

Re: Nombre premiers

Message par Asymetric » 15 févr. 2011 20:31

En effet, il est clairement évident que ces 2 nombres sont des nombres premiers.
Toute grandeur mesurable est valeur propre d'un endomorphisme.
Toute chose compréhensible est inintéressante.
Tout espace vérifie la propriété de Borel-Lebesgue si et seulement s'il vérifie la propriété de Bolzano-Weierstrass.

Messages : 1153

Enregistré le : 09 avr. 2010 16:49

Re: Nombre premiers

Message par compol » 15 févr. 2011 20:46

Ah bon? J'aimerai bien avoir une démo si possible astucieuse ! (sans passer par l'ordi)

Messages : 1418

Enregistré le : 31 août 2006 11:59

Re: Nombre premiers

Message par Valvino » 15 févr. 2011 21:21


Messages : 2382

Enregistré le : 22 juil. 2008 02:29

Re: Nombre premiers

Message par Asymetric » 15 févr. 2011 21:44

compol a écrit :Ah bon? J'aimerai bien avoir une démo si possible astucieuse ! (sans passer par l'ordi)
C'était une blague -.-

(Enfin une démo astucieuse serait d'utiliser Google pour avoir la liste des nombres premiers connus à ce jour, et de voir que les nombres en question de Dadin sont bien dans la liste, et en montrant que ces deux nombres sont biens distincts hein).
Toute grandeur mesurable est valeur propre d'un endomorphisme.
Toute chose compréhensible est inintéressante.
Tout espace vérifie la propriété de Borel-Lebesgue si et seulement s'il vérifie la propriété de Bolzano-Weierstrass.

Messages : 11293

Enregistré le : 30 juil. 2008 16:59

Classe : Dr.-Ing

Re: Nombre premiers

Message par fakbill » 15 févr. 2011 21:53

Pas prof.
Prépa, école, M2, thèse (optique/images) ->ingé dans le privé.

Messages : 790

Enregistré le : 23 oct. 2008 23:49

Re: Nombre premiers

Message par Dadin » 16 févr. 2011 00:40

Par contre une vraie question d'algo et de complexité intéressante qui me travaille depuis tout à l'heure est : "peut-on faire mieux que l'algorithme d'Euclide" pour trouver le PGCD de deux nombres ?
Ce dernier travaille en temps linéaire en la taille de l'entrée (cas le pire avec les nombres de Fibonacci). Donc on ne risque pas de trouver mieux en puissance polynomiale (faut bien lire l'entrée, mais preuve rigoureuse ?), mais améliorer de façon conséquente la constante par un autre algo ?

Avatar du membre
LB

Messages : 1059

Enregistré le : 09 juin 2008 14:14

Localisation : par rapport à un idéal maximal

Re: Nombre premiers

Message par LB » 16 févr. 2011 07:35

Apparemment y'a des trucs cools en base 2...
http://perso.ens-lyon.fr/damien.stehle/ ... slides.pdf

Pas forcément très compréhensible comme ça en le lisant vu que c'est un diaporama, mais ça doit donner quelques pistes et quelques références.
On peut dire que les fonctions convexes en dimension infinie et les fonctions continues en dimension finie sont d’une complexité similaire - Gilles Godefroy
http://perso.eleves.bretagne.ens-cachan.fr/~ldiet783/

Messages : 173

Enregistré le : 15 sept. 2007 23:12

Re: Nombre premiers

Message par nafpy » 16 févr. 2011 11:13

Dadin a écrit :... "peut-on faire mieux que l'algorithme d'Euclide" pour trouver le PGCD de deux nombres ?
...?
Dans l'absolu, La reponse est NON, on ne sait pas faire mieux depuis 2500 ans.
La seule source fiable restera "Donald Knuth, The Art of Computer Programming, Volume 2: Seminumerical Algorithms".
Et c'est là que j'avais decouvert (il y a +sieurs années), la seule amélioration d'Euclide "pratique", proposée par un certain J. Stein: Computational problems associated with Racah algebra. Journal of Computational Physics, Vol. 1, No. 3, pp. 397–405, 1967.
Pour en savoir un peu plus : http://en.wikipedia.org/wiki/Binary_GCD_algorithm
Quand à:
LB a écrit :Apparemment y'a des trucs cools en base 2...
http://perso.ens-lyon.fr/damien.stehle/ ... slides.pdf
C'est une plaisanterie... :P ... Trop de verbiage pour pas grand chose. Un algorithme pour être efficace, doit être facilement implémentable en pratique. S'il requiert une machine spécialisée, il perdra son interêt, à moins de ne s'interesser uniquement à l'evaluation théorique de la complexité.
Pour en dire un peu plus, L'algo peut être modifié pour le calcul des inverses modulaires.
A noter cependant une variante interessante est dans "B.S.Kaliski Jr. The Montgomery inverse and its applications".
Bonne lecture à tous ceux que la théorie et la pratique des nombres interesse.
Parent d'elèves ...

Messages : 11293

Enregistré le : 30 juil. 2008 16:59

Classe : Dr.-Ing

Re: Nombre premiers

Message par fakbill » 16 févr. 2011 16:14

Ca date un peu comme référence. Volume 2, Seminumerical Algorithms (troisième édition 1997).
A l'époque le test de primalité n'était pas P.

Dans mathematica, ils font ça:
"GCD interleaves the HGCD algorithm, the Jebelean\[Dash]Sorenson\[Dash]Weber accelerated GCD algorithm, and a combination of Euclid's algorithm and an algorithm based on iterative removal of powers of 2."
Pas prof.
Prépa, école, M2, thèse (optique/images) ->ingé dans le privé.

Répondre