Complexité de l'affacturage dans les champs numériques

25

Que sait-on de la complexité de calcul de la factorisation d'entiers dans des champs de nombres généraux? Plus précisement:

  1. Sur les entiers, nous représentons des entiers via leurs extensions binaires. Quelles sont les représentations analogues d'entiers dans des champs numériques généraux?
  2. Est-il connu que la primauté sur les champs numériques est en P ou BPP?
  3. Quels sont les algorithmes les plus connus pour factoriser les champs numériques? (Faites l' expn et la (apparemment)expn1/3 algorithmes étendentpartirZ?) Ici, factorisation se réfère à trouvercertaine représentation d'un nombre (représenté parnbits) comme produit de nombres premiers.
  4. Quelle est la complexité de trouver toutes les factorisations d'un entier dans un champ numérique? De compter combien de factorisations distinctes il a?
  5. Sur Z on sait que décider si un nombre donné a un facteur dans un intervalle [a,b] est NP-difficile. Sur l'anneau des nombres entiers dans les champs numériques, peut-il être le cas où trouver s'il existe un facteur premier dont la norme est dans un certain intervalle est déjà NP-difficile?
  6. L'affacturage est-il dans les champs numériques de BQP?

Remarques, motivations et mises à jour.

Bien sûr, le fait que la factorisation n'est pas unique sur les champs numériques est crucial ici. La question (en particulier la partie 5) était motivée par ce billet de blog sur GLL (voir cette remarque ), et aussi par cette question antérieure de TCSexchange. Je l'ai également présenté sur mon blog où Lior Silverman a présenté une réponse complète .

Gil Kalai
la source
Pouvez-vous donner un exemple? en quoi l'affacturage dans les champs defn est-il différent de l'affacturage entier simple?
vzn
2
Pour (0): Je suppose généralement un corps de nombres est représenté par Q [ ξ ] /φ φ est un polynôme irréductible. Ensuite, un élément de K est un tuple de paires ( ( n 0 , ( φ ) . Cela signifie que votre élément est n 0 / d 0 + n 1 ξ / dKQ[ξ]/φφK δ = deg((n0,d0),(n1,d1),,(nδ1,dδ1))δ=deg(φ) . n0/d0+n1ξ/d1++nδ1ξδ1/dδ1
Bruno
2
@Gil Avez-vous déjà vu ce livre? springer.com/mathematics/numbers/book/978-3-540-55640-4 Je n'ai pas accès à ma copie pour le moment (même si je le ferai à nouveau dans quelques jours, et je vérifierai cela). Je voudrais voir s'il y a quelque chose d'écrit sur la factorisation dans (i) les champs de nombres algébriques, ou (ii) les domaines Dedekind, avec le numéro de classe> 1.
Daniel Apon
4
@vzn: Sans mettre de mots dans la bouche de Gil, je suis presque sûr qu'il veut dire des extensions finies des raisonnements (exactement ce à quoi vous avez lié). Quand il dit "factoriser dans un tel champ", je suis presque sûr qu'il veut dire factoriser dans l'anneau d'entiers d'un tel champ. La même page wikipedia à laquelle vous avez lié a une section sur l'anneau d'entiers dans un champ de nombre algébrique.
Joshua Grochow
1
@vzn Le tamis de champ numérique utilise des champs numériques pour factoriser les entiers.
Yuval Filmus

Réponses:

14

La réponse suivante a été initialement publiée sous forme de commentaire sur le blog de Gil

(1) Soit un champ numérique, où nous supposons que α a un polynôme monique minimal f Z [ x ] . On peut alors représenter des éléments de l'anneau d'entiers O K sous forme de polynômes en α ou en termes de base intégrale - les deux sont équivalents.K=Q(α)αfZ[x]OKα

Maintenant , fixant comme dans (1) il y a une réduction du temps polynomial du problème sur K au problème en Q . Pour vérifier que les calculs (par exemple coupant un idéal avec Z ou factorisant un mod polynomial p ) peuvent être effectués en temps polynomial, voir le livre de Cohen mentionné dans la réponse précédente.KKQZp

En tant que précalcul pour chaque nombre rationnel divisant le discriminant de α (c'est-à-dire le discriminant de f ), trouver tous les nombres premiers de O K situés au-dessus de p .pαfOKp

(2) Pour le test de primalité, étant donné un idéal soit p Z tel que aZ = p Z (cela peut être calculé en temps polynomial et le nombre de bits de p est polynomial en entrée). Vérifiez dans le temps polynomial si p est premier. Sinon, a n'est pas premier. Si oui, alors trouver les nombres premiers de O K situés au-dessus de p soit à partir du précalcul, soit en factorisant f mod p . Dans tous les cas, si a est premier, il doit être l'un de ces nombres premiers.aOKpZaZ=pZppaOKpfpa

(3a), (6a) Pour la factorisation en nombres premiers, étant donné un idéal trouver sa norme y = N K Q ( a ) = [ O K : a ] . Encore une fois, cela peut être trouvé en temps polynomial et n'est donc pas trop grand. Facteur yaOKy=NQK(a)=[OK:a]y en (soit classiquement, soit en utilisant l'algorithme de Shor, selon la réduction que vous souhaitez). Cela donne une liste de nombres premiers rationnels divisant y , et donc comme dans 2, nous pouvons trouver la liste des nombres premiers de O K divisant y . Depuis un | yZyOKy cela donne la liste des nombres premiers divisant a . Enfin, il est facile de déterminer l'exposant auquel un nombre premier divise un idéal donné.a|yOKa

(3b), (6b) Mais Gil veut la factorisation en irréductibles, pas en nombres premiers. Il s'avère que, étant donné la factorisation première de il est possible de construire efficacement une factorisation de xxOKx en éléments irréductibles de . Pour cela, soit h K le numéro de classe, et notons qu'il est possible de calculer efficacement la classe idéale d'un idéal donné. Maintenant, pour trouver un diviseur irréductible de x, sélectionnez h K idéaux premiers (éventuellement avec répétition) à partir de la factorisation de xOKhKxhKx. Selon le principe du pigeonnier, un sous-ensemble de ces multiplications se transforme en identité dans le groupe de classe; trouver un tel sous-ensemble minimal. Son produit est alors un idéal principal généré par un élément irréductible. Divisez par cet élément, supprimez les idéaux pertinents de la factorisation et répétez. Si la factorisation a moins de h K éléments, il suffit de prendre un sous-ensemble minimal de tous les facteurs.xhK

(4) Je pense qu'il est possible de compter les factorisations en irréductibles, mais c'est un peu de combinatoire supplémentaire - donnez-moi s'il vous plaît le temps de travailler. D'un autre côté, la détermination de chacun d'eux n'est pas intéressante dans le contexte des algorithmes de factorisation sous-exponentielle car il existe en général de façon exponentielle beaucoup de telles factorisations.

(5) Je n'en ai aucune idée.

Lior Silberman
la source
5

Comme mentionné par Daniel, vous pouvez trouver quelques informations dans le livre A Course in Computational Algebraic Number Theory ( lien ).

En particulier, il existe plusieurs façons de représenter des éléments de champs numériques. Soit un champ numérique avec φ un degrés - n monique polynôme irréductible de Z [ ξ ] . Soit θ n'importe quelle racine de φ . La représentation dite standard d'un élément α K est le tuple ( a 0K=Q[ξ]/φφnZ[ξ]θφαK(a0,,an1,d) , d > 0 et d ) = 1 , tels que α = 1aiZd>0gcd(a0,,an1,d)=1

α=1di=0n1aiθi.
Bruno
la source