Discuter:Décomposition en produit de facteurs premiers

Un article de Wikipédia, l'encyclopédie libre.

WikiProjet Mathématiques
 Décomposition en produit de facteurs premiers fait partie du projet Mathématiques, qui a pour but d'enrichir le contenu de Wikipédia sur les sujets liés aux mathématiques. Si vous voulez participer, vous pouvez modifier cet article ou visiter la page du projet, où vous pourrez vous joindre au projet et consulter la liste des tâches et des objectifs. Le portail Mathématiques pourrait aussi vous intéresser.
B Cet article a été classé comme d'Avancement B selon le Tableau d'évaluation du projet. (Voir les statistiques)
Maximum Cet article a été classé comme d'Importance maximum selon le Tableau d'évaluation du projet.

Sommaire

[modifier] Lien externe mort

Bonjour,

Pendant plusieurs vérifications automatiques, un lien était indisponible. Merci de vérifier si il est bien indisponible et de le remplacer par une version archivée par Internet Archive si c'est le cas. Vous pouvez avoir plus d'informations sur la manière de faire ceci ici. Les erreurs rapportées sont :

▪ Eskimbot ☼ 31 janvier 2006 à 01:52 (CET)

[modifier] GNFS

Je ne m'y connais pas en complexité algorithmique mais la formule

\Theta\left(\exp\left( \left(\frac{64}{9}n\right)^{\frac{1}{3}} (\ln\ln n)^{\frac{2}{3}} \right)\right).

est très probablement fausse

l'ancienne formule

\Theta\left(\exp\left( \left(\frac{64}{9}n\right)^{\frac{1}{3}} (\log n)^{\frac{2}{3}} \right)\right).

ne correspond pas à la forrmule sur l'article GNFS.

O\left(\exp\left( \left(\frac{64}{9}\log n\right)^{\frac{1}{3}} (\log (\log n))^{\frac{2}{3}} \right)\right).

Même en tenant compte que n ne représente pas la même chose dans chaque article. Ici n représente le nombre de bits occupés par le nombre, dans l'autre article n représente le nombre lui-même. Mais que je sache le nombre de bits occupés par le nombre n n'est pas logn mais log2(n).

Bref, j'ai supprimé la formule de l'article et je laisse un spécialiste de l'algorithmique débroussailler tout ça. HB 31 mai 2006 à 22:26 (CEST)

[modifier] Problème NP-Complet et ordinateur quantique

J'ajoute que le problème de la factorisation en nombre premier par un ordinateur quantique ne remet pas en cause la difficulté du problème. Si je ne m'abuse, un ordinateur quantique est non-déterministe et permet donc de résoudre des problème Non déterministe Polynomiaux en temps polynomial.

Il y a une différence entre machine quantique et machine non-déterministe.

[modifier] But spécial ou but général ?

Bonjour,
La méthode de factorisation de Fermat n'est-elle pas une méthode à but général...? Les autres de cette section sont aussi basées sur la congruence de carrés... Sauf que son temps d'exécution dépend de la grandeur des facteurs de N, ce qui semble correspondre à l'intro de la section sur le but spécial... Je pense que je ne comprends pas bien cette classification des algorithmes... Gene.arboit 2 août 2006 à 22:30 (CEST)