# Complexity of factoring in number fields

What is known about the computational complexity of factoring integers in general number fields? More specifically:

1. Over the integers we represent integers via their binary expansions. What is the analogous representations of integers in general number fields?
2. Is it known that primality over number fields is in P or BPP?
3. What are the best known algorithms for factoring over number fields? (Do the $\exp \sqrt n$ and the (apparently) $\exp n^{1/3}$ algorithms extend from $\mathbb{Z}$?) Here, factoring refers to finding some representation of a number (represented by $n$ bits) as a product of primes.
4. What is the complexity of finding all factorizations of an integer in a number field? Of counting how many distinct factorizations it has?
5. Over $\mathbb{Z}$ it is known that deciding if a given number has a factor in an interval $[a,b]$ is NP-hard. Over the ring of integers in number fields, can it be the case that finding if there is a prime factor whose norm is in a certain interval is already NP-hard?
6. Is factoring in number fields in BQP?

Of course the fact that factorization is not unique over number fields is crucial here. The question (especially part 5) was motivated by this blog post over GLL (see this remark), and also by this earlier TCSexchange question. I presented it also over my blog where Lior Silverman presented a thorough answer.

• can you give an example? how is factoring in fields defn different than straight integer factoring? – vzn Jan 24 '13 at 21:10
• For (0): I guess usually a number field $\mathbb K$ is represented as $\mathbb Q[\xi]/\langle\varphi\rangle$ where $\varphi$ is an irreducible polynomial. Then, an element of $\mathbb K$ is a tuple of pairs $((n_0,d_0),(n_1,d_1),\dotsc,(n_{\delta-1},d_{\delta-1}))$ where $\delta=\deg(\varphi)$. This means that your element is $n_0/d_0+n_1\xi/d_1+\dotsb+n_{\delta-1}\xi^{\delta-1}/d_{\delta-1}$. – Bruno Jan 25 '13 at 12:33
• @Gil Have you seen this book before? springer.com/mathematics/numbers/book/978-3-540-55640-4 I don't have access to my copy at the moment (though I will again in a few days, and will check on this). I would look to see if there is anything written about factorization in (i) algebraic number fields, or (ii) Dedekind domains, with class number > 1. – Daniel Apon Jan 26 '13 at 4:26
• @vzn: Without putting words in Gil's mouth, I'm pretty sure he means finite extensions of the rationals (exactly what you linked to). When he says "factoring in such a field", I'm pretty sure he means factoring in the ring of integers of such a field. The same wikipedia page you linked to has a section on the ring of integers in an algebraic number field. – Joshua Grochow Jan 28 '13 at 16:55
• @vzn The number-field sieve uses number fields to factor integers. – Yuval Filmus Feb 1 '13 at 23:01

The following answer was originally posted as a comment on Gil's blog

(1) Let $K=\mathbb{Q}(\alpha)$ be a number field, where we assume $\alpha$ has a monic minimal polynomial $f\in\mathbb{Z}[x]$. One can then represent elements of the ring of integers $\mathcal{O}_K$ as polynomials in $\alpha$ or in terms of an integral basis -- the two are equivalent.

Now fixing $K$ as in (1) there's a polynomial-time reduction from the problem over $K$ to the problem in $\mathbb{Q}$. To verify that the computations (e.g. intersecting an ideal with $\mathbb{Z}$ or factoring a polynomial mod $p$) can be done in polynomial time see Cohen's book referred to in the previous answer.

As a precomputation for each rational prime $p$ dividing the discriminant of $\alpha$ (that is the discriminant of $f$) find all primes of $\mathcal{O}_K$ lying above $p$.

(2) For primality testing, given an ideal $\mathfrak{a}\triangleleft\mathcal{O}_K$ let $p\in\mathbb{Z}$ be such that $\mathfrak{a}\cap\mathbb{Z} = p\mathbb{Z}$ (this can be computed in polynomial time and the number of bits of $p$ is polynomial in the input). Check in polynomial time whether $p$ is prime. If not then $\mathfrak{a}$ is not prime. If yes then find the primes of $\mathcal{O}_K$ lying above $p$ either from the precomputation or by factoring $f$ mod $p$. In any case if $\mathfrak{a}$ is prime it must be one of those primes.

(3a),(6a) For factoring into primes, given an ideal $\mathfrak{a}\triangleleft\mathcal{O}_K$ find its norm $y = N^K_\mathbb{Q}(\mathfrak{a}) = [\mathcal{O}_K:\mathfrak{a}]$. Again this can be found in polynomial time and consequently is not too large. Factor $y$ in $\mathbb{Z}$ (either classically or using Shor's algorithm, depending on the reduction you want). This gives a list of rational primes dividing $y$, and hence as in 2 we can find the list of primes of $\mathcal{O}_K$ dividing $y$. Since $\mathfrak{a} | y\mathcal{O}_K$ this gives the list of primes dividing $\mathfrak{a}$. Finally it is easy to determine the exponent to which a prime divides a given ideal.

(3b),(6b) But Gil wants factorization into irreducibles, not into primes. It turns out that given the prime factorization of $x\mathcal{O}_K$ it is possible to efficiently construct one factorization of $x$ into irreducible elements of $\mathcal{O}_K$. For this let $h_K$ be the class number, and note that it is possible to efficiently compute the ideal class of a given ideal. Now to find an irreducible divisor of $x$ select $h_K$ prime ideals (possibly with repetition) from the factorization of $x$. By the pigeon-hole principle some subset of those multiplies to the identity in the class group; find a minimal such subset. Its product is then a principal ideal generated by an irreducible element. Divide $x$ by this element, remove the relevant ideals from the factorization and repeat. If the factorization has less than $h_K$ elements then just take a minimal subset of all the factors.

(4) I think it's possible to count the factorizations into irreducibles, but this is a bit of extra combinatorics -- please give me time to work it out. One the other hand, determining all of them is not interesting in the context of sub-exponential factorization algorithms since there are in general exponentially many such factorizations.

(5) I have no idea.

As mentioned by Daniel, you can find some informations in the book A Course in Computational Algebraic Number Theory (link).

In particular, there are several ways of representing elements of number fields. Let $K=Q[\xi]/\langle\varphi\rangle$ be a number field with $\varphi$ a degree-$n$ monic irreducible polynomial of $\mathbb Z[\xi]$. Let $\theta$ be any root of $\varphi$. The so-called standard representation of an element $\alpha\in K$ is the tuple $(a_0,\dotsc,a_{n-1},d)$ where $a_i\in\mathbb Z$, $d>0$ and $\gcd(a_0,\dotsc, a_{n-1},d)=1$, such that $$\alpha=\frac{1}{d} \sum_{i=0}^{n-1} a_i\theta^i.$$