Tag Archives: Primality

Primality and Factoring in Number Fields

Both PRIMALITY – deciding if an integer n is a prime and FACTORING – representing an integer as a product of primes, are algorithmic questions of great interest. I am curious to know what is known about these questions over general number fields. A major difference there is that there is know unique factorization to primes. Let me repeat here a question that I asked over TCS-stackexchange.

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

0. Over the integers we represent integers via their binary expansions. What is the analogous representations of integers in general number fields?

1. Is it known that primality over number fields is in P or BPP?

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

3. What is the complexity of finding all factorizations of an integer in a number field? Of counting how many distinct factorizations it has?

4. 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?

5. Is factoring in number fields in BQP?

Motivation and updates: The question (especially part 5) was motivated by this blog post over GLL (see this remark), and also by an earlier TCSexchange question. Lior Silverman presented in the comment section  below  a thorough answer.