Why going to number fields in number field sieve help beat quadratic sieve?

Question

To factor an $n$ bit integer number field sieve roughly takes $$e^{c{(\ln\ln n)^{\frac23}}({\ln n})^{\frac13}}$$ time while quadratic sieve takes $$e^{c{(\ln\ln n)^{\frac12}}({\ln n})^{\frac12}}$$ time.

What does number field sieve improve on quadrative sieve? I know we work with number fields and other details. However what exact complexity reason are we able to improve and why cannot we improve any further?

I know wiki has a few sentence explanation in comments. However it is difficult to pinpoint both why quadratic sieve was beaten and why no other alternative has been known for two decades.

---

In other words why does looking at abelian extensions of number fields help?

Which extensions help and why?

Answer 1

I think Carl Pomerance gets very close to giving a complete answer to the first part of you question, in the survey mentioned by Carlo Beenakker in the comments.

Perhaps it is not clear why the number field sieve is a good factoring algorithm. A key quantity in a factorization method such as the quadratic sieve or the number field sieve is what I was calling "$X$" earlier. It is an estimate for the size of the auxiliary numbers that we are hoping to combine into a square. Knowing $X$ gives you the complexity; it is about $\exp(\sqrt{2 \log X \log \log X})$. In the quadratic sieve we have X about $n^{1/2+\epsilon}$. But in the number field sieve, we may choose the polynomial $f(x)$ and the integer $m$ in such a way that $(a-mb)N(a-\alpha b)$ (the numbers that we hope to find smooth) is bounded by a value of $X$ of the form $\exp (c' (\log > n)^{2/3})(\log \log n)^{1/3}))$. Thus the number of digits of the auxiliary numbers that we sieve over for smooth values is about the $2/3$ power of the number of digits of $n$, as opposed to the quadratic sieve where the auxiliary numbers have more than half the number of digits of $n$. That is why the number field sieve is asymptotically so fast in comparison.

Pages from 7 to 10 of the survey are particularly relevant, although the whole paper is defenitely worth reading.

• Carl Pomerance, A Tale of Two Sieves (1996)

For a more technical and concrete exposition, you might be interested in:

• Carl Pomerance, The Number Field Sieve (1994)

• J. P. Buhler, H. W. Lenstra, Carl Pomerance, Factoring integers with the number field sieve (1993)

As for the second part, question of the type "why can't we prove/improve __" are usually hard or impossible to answer, except in cases where there is a well know obstruction.

In particular, we can't rule out that the number field sieve is the best possible. Take for example this fragment from Anirban Pathak's "Elements of Quantum Computation and Quantum Communication":

[...] This indicates that factorization is a computational problem which does not belong to $P$ and belongs to $NP$. This suggests that $P \subsetneq NP$. We reach this conclusion by considering the number field sieve algorithm as the best algorithm. However, we cannot exclude the possibility that tomorrow someone may invent an efficient classical algorithm for factorization.

Answer 2

Each relation in the quadratic sieve has to factor integers of size near the square root of N. In contrast, each relation in the number field sieve has to factor two things, a number and an element of a number field. That number field can be chosen so that the two factorizations are much easier than the factorization in the quadratic sieve. The number field is chosen in terms of a polynomial of degree d, and as N increases in size the value of d is increased. The asymptotic complexity of NFS assumes the optimal value of d