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

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

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?
Est-il connu que la primauté sur les champs numériques est en P ou BPP?
Quels sont les algorithmes les plus connus pour factoriser les champs numériques? (Faites l' $\exp \sqrt n$ et la (apparemment) $\exp n^{1/3}$ algorithmes étendentpartir $\mathbb{Z}$ ?) Ici, factorisation se réfère à trouvercertaine représentation d'un nombre (représenté par $n$ bits) comme produit de nombres premiers.
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?
Sur $\mathbb{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?
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 .

cc.complexity-theory nt.number-theory comp-number-theory 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

Pour (0): Je suppose généralement un corps de nombres

est représenté par

où

est un polynôme irréductible. Ensuite, un élément de

est un tuple de paires

. Cela signifie que votre élément est

K

$\mathbb K$

Q [ξ] / ⟨ φ ⟩

$\mathbb Q[\xi]/\langle\varphi\rangle$

φ

$\varphi$

K

$\mathbb K$

où

((n_{0}, d_{0}), (n_{1}, d_{1}), \dots, (n_{δ - 1}, d_{δ - 1}))

$((n_0,d_0),(n_1,d_1),\dotsc,(n_{\delta-1},d_{\delta-1}))$

δ = \deg (φ)

$\delta=\deg(\varphi)$

n_{0} / d_{0} + n_{1} ξ / d_{1} + \dots + n_{δ - 1} ξ^{δ - 1} / d_{δ - 1}

$n_0/d_0+n_1\xi/d_1+\dotsb+n_{\delta-1}\xi^{\delta-1}/d_{\delta-1}$

Bruno

@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

@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

@vzn Le tamis de champ numérique utilise des champs numériques pour factoriser les entiers.

Yuval Filmus

Réponses:

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 . On peut alors représenter des éléments de l'anneau d'entiers sous forme de polynômes en ou en termes de base intégrale - les deux sont équivalents. $K=\mathbb{Q}(\alpha)$ $\alpha$ $f\in\mathbb{Z}[x]$ $\mathcal{O}_K$ $\alpha$

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

En tant que précalcul pour chaque nombre rationnel divisant le discriminant de (c'est-à-dire le discriminant de ), trouver tous les nombres premiers de situés au-dessus de . $p$ $\alpha$ $f$ $\mathcal{O}_K$ $p$

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

(3a), (6a) Pour la factorisation en nombres premiers, étant donné un idéal trouver sa norme . Encore une fois, cela peut être trouvé en temps polynomial et n'est donc pas trop grand. Facteur $\mathfrak{a}\triangleleft\mathcal{O}_K$ $y = N^K_\mathbb{Q}(\mathfrak{a}) = [\mathcal{O}_K:\mathfrak{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 , et donc comme dans 2, nous pouvons trouver la liste des nombres premiers de divisant . Depuis $\mathbb{Z}$ $y$ $\mathcal{O}_K$ $y$ cela donne la liste des nombres premiers divisant . Enfin, il est facile de déterminer l'exposant auquel un nombre premier divise un idéal donné. $\mathfrak{a} | y\mathcal{O}_K$ $\mathfrak{a}$

(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 $x\mathcal{O}_K$ $x$ en éléments irréductibles de . Pour cela, soit 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 sélectionnez idéaux premiers (éventuellement avec répétition) à partir de la factorisation de $\mathcal{O}_K$ $h_K$ $x$ $h_K$ $x$ . 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 éléments, il suffit de prendre un sous-ensemble minimal de tous les facteurs. $x$ $h_K$

(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

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 - monique polynôme irréductible de . Soit n'importe quelle racine de . La représentation dite standard d'un élément est le tuple $K=Q[\xi]/\langle\varphi\rangle$ $\varphi$ $n$ $\mathbb Z[\xi]$ $\theta$ $\varphi$ $\alpha\in K$ $(a_0,\dotsc,a_{n-1},d)$ où , et , tels que $a_i\in\mathbb Z$ $d>0$ $\gcd(a_0,\dotsc, a_{n-1},d)=1$

α = \frac{1}{d} \sum_{i = 0}^{n - 1} a_{i} θ^{i} .

$\alpha=\frac{1}{d} \sum_{i=0}^{n-1} a_i\theta^i.$

Bruno
la source