Nombre premiers

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

Messages : 173

Enregistré le : 15 sept. 2007 23:12

Re: Nombre premiers

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

fakbill a écrit :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."
Bien sur que ça date, n'empeche que ça reste la meilleure réference pour les applications pratiques. De toute les façons toutes les améliorations sont déduites de J. Stein, et la complexité théorique reste quadratique en le longueur des opérandes.
Je ne connais pas la version de Jebelean, et je t'en dirai plus si j'arrive à me la procurer. De toute façon si tu as d'autres références, je suis preneur.
Le test de Primalité n'etait pas P, à l'epoque, mais dans la pratique, pour des raisons de performance on continue toujours avec les méthodes probabilistes qui fournissent un bon résultat tant que la conjecture de Riemman n'est pas infirmée. Mais sûr que le trio a fait avancer les choses dans ce domaine.
Parent d'elèves ...

Messages : 11339

Enregistré le : 30 juil. 2008 16:59

Classe : Dr.-Ing

Re: Nombre premiers

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

Oui oui c'est la diférence entre la pratique et la théorie en algo.
En pratique, un facteur 2 c'est souvent la différence entre "acceptable" et "trop lent"....en théorie, on crie victoire quand on gagne une classe de complexité ou quand on réduit un peu un exposant...la constante est cachée dans le O :D

Même la multiplication rapide...je ne m'en sert jamais car je n'ai jamais besoin d'une précision infinie sur des entiers....mais c'est cool de savoir que ca existe.
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 18:21

L'algorithme en binaire est quand même un brin décevant, il s'agit du même algorithme que celui d'Euclide avec des astuces de calculs processeur. Mais merci quand même pour les différents liens !

nafpy : une autre conjecture (et, je trouve, la plus belle en théorie de la complexité) est que tout ce qui se fait en temps polynomial probabiliste ($ \mathbf{BPP} $) peut se faire en temps polynomial déterministe ($ \mathbf{P} $). Le fait que la primalité soit en fait $ \mathbf{P} $ n'était donc pas si surprenant !

fabkill : la multiplication rapide est quand même indispensable si l'on travail sur des grands entiers (à partir d'une vingtaine-trentaine de chiffres Karatsuba est vraiment mieux, et au delà d'une grosse cinquantaine FFT rulz). Après c'est sur que pour manipuler des entiers de 10 chiffres la multiplication naïve reste la plus efficace.

Messages : 11339

Enregistré le : 30 juil. 2008 16:59

Classe : Dr.-Ing

Re: Nombre premiers

Message par fakbill » 16 févr. 2011 18:25

. Le fait que la primalité soit en fait \mathbf{P} n'était donc pas si suprenant !

Surprenant non mais ce qui l'était c'était que je pouvais comprendre sans problème leur algo :) C'est une approche "simple" qui a payé.
Pas prof.
Prépa, école, M2, thèse (optique/images) ->ingé dans le privé.

Répondre