<p><em>The following answer was originally posted as a comment on Gil's blog</em></p>

<p>(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.</p>

<p>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.</p>

<p>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$.</p>

<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.</p>

<p>(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.</p>

<p>(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 <em>one</em> 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.</p>

<p>(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.</p>

<p>(5) I have no idea.</p>

CC BY-SA 3.0
2013-02-01T08:27:23.220Z
2013-02-01T08:27:23.220Z
Lior Silberman
<p>As mentioned by Daniel, you can find some informations in the book <em>A Course in Computational Algebraic Number Theory</em> (<a href="http://www.springer.com/mathematics/numbers/book/978-3-540-55640-4">link</a>). </p>

<p>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 <em>standard representation</em> of an element $\alpha\in K$ is the tuple $(a_0,\dotsc,a_{n-1},d)$ where $a_i\in\mathbb Z$, $d&gt;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.$$</p>

CC BY-SA 3.0
2013-01-28T08:57:01.037Z
2013-01-28T08:57:01.037Z
Bruno
<p>What is known about the computational complexity of factoring integers in general number fields? More specifically:</p>
<ol>
<li>Over the integers we represent integers via their binary expansions. What is the analogous representations of integers in general number fields?</li>
<li>Is it known that primality over number fields is in P or BPP?</li>
<li>What are the best known algorithms for factoring over number fields? (Do the <span class="math-container">$\exp \sqrt n$</span> and the (apparently) <span class="math-container">$\exp n^{1/3}$</span> algorithms extend from <span class="math-container">$\mathbb{Z}$</span>?) Here, factoring refers to finding some representation of a number (represented by <span class="math-container">$n$</span> bits) as a product of primes.</li>
<li>What is the complexity of finding all factorizations of an integer in a number field? Of counting how many distinct factorizations it has?</li>
<li>Over <span class="math-container">$\mathbb{Z}$</span> it is known that deciding if a given number has a factor in an interval <span class="math-container">$[a,b]$</span> 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?</li>
<li>Is factoring in number fields in BQP?</li>
</ol>
<h3>Remarks, motivations and updates.</h3>
<p>Of course the fact that factorization is not unique over number fields is crucial here. The question (especially part 5) was motivated by this <a href="http://rjlipton.wordpress.com/2012/09/26/how-not-to-prove-integer-factoring-is-in-p/" rel="noreferrer">blog post over GLL</a> (see <a href="http://rjlipton.wordpress.com/2012/09/26/how-not-to-prove-integer-factoring-is-in-p/#comment-27156" rel="noreferrer">this remark</a>), and also by this earlier TCSexchange question. I presented it also <a href="http://gilkalai.wordpress.com/2013/01/28/primality-and-factoring-in-number-fields/" rel="noreferrer">over my blog</a> where Lior Silverman <a href="http://gilkalai.wordpress.com/2013/01/28/primality-and-factoring-in-number-fields/#comment-8000" rel="noreferrer">presented a thorough answer</a>.</p>

CC BY-SA 3.0
2013-01-24T21:10:02.033Z
can you give an example? how is factoring in fields defn different than straight integer factoring?
vzn
CC BY-SA 3.0
2013-01-25T02:59:28.830Z
Dear vzn, the main difference is that in general number fields there is no unique factorization. (I will add some background to the question later.)
Gil Kalai
CC BY-SA 3.0
2013-01-25T05:30:10.870Z
ok, is there any similarity to ideals in number theory which do not admit unique factorization?
vzn
CC BY-SA 3.0
2013-01-25T09:10:17.190Z
I am not an expert, but I don't see a natural way that this problem would reduce to the hidden subgroup problem. So I would be (happily) surprised if this problem turns out to be in BQP.
Shitikanth
CC BY-SA 3.0
2013-01-25T12:33:25.623Z
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
CC BY-SA 3.0
2013-01-26T04:07:26.310Z
@Bruno This is an answer (for a part of the question); you should post it as an answer. :)
Daniel Apon
CC BY-SA 3.0
2013-01-26T04:26:38.407Z
@Gil Have you seen this book before?

http://www.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
CC BY-SA 3.0
2013-01-26T04:33:58.887Z
In fact, I'm fairly interested in the answers to these questions myself.. I can probably find other dead trees with information on the topic laying around somewhere. (These questions seem like something that would have found their way into book form at some point.) Or, maybe someone else will know quicker than that. :)
Daniel Apon
CC BY-SA 3.0
2013-01-26T20:26:58.503Z
can someone plz clarify via a std ref/defn or cite an online ref on what kind of number field is being referred to? is it referred to on wikipedia? is this different than [algebraic number field](http://en.wikipedia.org/wiki/Algebraic_number_field)? also note an old classic factoring algorithm is [GNFS](http://en.wikipedia.org/wiki/General_number_field_sieve) which works on "number fields"...?
vzn
CC BY-SA 3.0
2013-01-26T20:33:09.397Z
also [binary fields](http://en.wikipedia.org/wiki/Binary_field) can operate on bitwise vectors?
vzn
CC BY-SA 3.0
2013-01-28T16:55:07.957Z
@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
CC BY-SA 3.0
2013-02-01T23:01:06.687Z
@vzn The number-field sieve uses number fields to factor integers.
Yuval Filmus
CC BY-SA 3.0
2015-07-25T07:21:02.747Z
Does statement number $5$ above which states that "Over $\Bbb Z$ it is known that deciding if a given number has a factor in an interval $[a,b]$ is $\mathsf{NP}$-hard" have a formal proof?
Turbo
<cc.complexity-theory><nt.number-theory><comp-number-theory>
Complexity of factoring in number fields
Gil Kalai
# Complexity of factoring in number fields

(Asked by: username_0 on 2013-01-24)

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?

### Remarks, motivations and updates.

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](http://rjlipton.wordpress.com/2012/09/26/how-not-to-prove-integer-factoring-is-in-p/) (see [this remark](http://rjlipton.wordpress.com/2012/09/26/how-not-to-prove-integer-factoring-is-in-p/#comment-27156)), and also by this earlier TCSexchange question. I presented it also [over my blog](http://gilkalai.wordpress.com/2013/01/28/primality-and-factoring-in-number-fields/) where Lior Silverman [presented a thorough answer](http://gilkalai.wordpress.com/2013/01/28/primality-and-factoring-in-number-fields/#comment-8000).

**Tags:** cc.complexity-theory, nt.number-theory, comp-number-theory
> **Comments:**
> **username_1**: can you give an example? how is factoring in fields defn different than straight integer factoring?  
> **username_0**: Dear vzn, the main difference is that in general number fields there is no unique factorization. (I will add some background to the question later.)  
> **username_1**: ok, is there any similarity to ideals in number theory which do not admit unique factorization?  
> **username_2**: I am not an expert, but I don't see a natural way that this problem would reduce to the hidden subgroup problem. So I would be (happily) surprised if this problem turns out to be in BQP.  
> **username_3**: 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}$.  
> **username_4**: @Bruno This is an answer (for a part of the question); you should post it as an answer. :)  
> **username_4**: @Gil Have you seen this book before?  http://www.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.  
> **username_4**: In fact, I'm fairly interested in the answers to these questions myself.. I can probably find other dead trees with information on the topic laying around somewhere. (These questions seem like something that would have found their way into book form at some point.) Or, maybe someone else will know quicker than that. :)  
> **username_1**: can someone plz clarify via a std ref/defn or cite an online ref on what kind of number field is being referred to? is it referred to on wikipedia? is this different than [algebraic number field](http://en.wikipedia.org/wiki/Algebraic_number_field)? also note an old classic factoring algorithm is [GNFS](http://en.wikipedia.org/wiki/General_number_field_sieve) which works on "number fields"...?  
> **username_1**: also [binary fields](http://en.wikipedia.org/wiki/Binary_field) can operate on bitwise vectors?  
> **username_5**: @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.  
> **username_6**: @vzn The number-field sieve uses number fields to factor integers.  
> **username_7**: Does statement number $5$ above which states that "Over $\Bbb Z$ it is known that deciding if a given number has a factor in an interval $[a,b]$ is $\mathsf{NP}$-hard" have a formal proof?  

---

## 2 answers

### Answer by username_8 on 2013-02-01. Score: 16

*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.


---

### Answer by username_3 on 2013-01-28. Score: 5

As mentioned by Daniel, you can find some informations in the book *A Course in Computational Algebraic Number Theory* ([link](http://www.springer.com/mathematics/numbers/book/978-3-540-55640-4)).

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.$$


---

