Does the ability to factor in polynomial time give you smooth numbers in the number field sieve?

Ian Campbell

8/1/24, 8:57 PM

I have read that despite strong connections between prime factorization and DLP an algorithm for the former does not imply the latter directly. But I was reading about the number field sieve and it seemed like the bottleneck was identifying smooth norms. Wouldn't an ultrafast prime factorization algorithm achieve that?

1 + 0

number-field-sieve

Score:1

Crypto

Daniel S

8/2/24, 6:45 AM

Being able to test for smooth norms quickly (e.g. polynomial time) is insufficient to quickly detect smooth norms in a large selection of candidates as the test must still be applied to a large number of candidates. Thus even if smooth norms could be identified in time $O(1)$, the log-asymptotic complexity of the number field sieve is unaffected. In fact sieving for smooth norms allows one to test $n$ candidates for $y$-smoothness in time and memory roughly $n\log\log y$ so that the parallelised smoothness test only takes an average $\log\log y$ work per candidate.

The bottleneck lies in the fact that $n$ cannot be too small or we will not find enough relations to produce a solvable linear algebra system. The cost to test the $n$ candidate norms is at best a second order effect (for example, the log asymptotic cost of the number field sieve is unchanged whether we test using sieving at cost $O(\log\log y)$ per candidate or ECM at cost $\exp((1+o(1))\sqrt{2\log y\log\log y})$ per candidate).

+ 8

Ian Campbell

8/2/24, 3:14 PM

Interesting. Wouldn't factoring larger smooth norms produce higher logs on the linear system which could precipitously drop n?

Daniel S

8/2/24, 3:19 PM

@IanCampbell No introducing a larger value of $y$ would make a greater proportion of candidates would succeed, but the number of successes required would also grow leading to an overall increase in $n$. Likewise, work of Croot, Granville, Peamantle and Tetali shows that there's no great hope of getting a solvable subsystem from a small subset of the relations.

Ian Campbell

8/2/24, 3:41 PM

One last question. What is the size of the smoothness bound? The best I've found is that it's x^(1/d) but I haven't found the optimal value of d. Are you sure about that complexity? The paper 'Smooth Numbers: Computational Number Theory and Beyond' States it as less than loglog(y)+uy on page 307. That's a huge difference if y is large

Ian Campbell

8/2/24, 3:55 PM

Also isn't the advantage in computational complexity of number and function field sieves compared to index calculus a smaller smoothness bound? That would imply higher n lower y which seems to imply the bottleneck is identifying smooth norms

Daniel S

8/3/24, 5:52 AM

The optimal smoothness bound is $y=\exp((2^{-1/2}+o(1))\sqrt{\log s\log\log s})$ where $s$ is the typical size of the numbers being tested for smoothness. This allows the optimal choice of $n$ (number of candidates) as $n=\exp((2^{1/2}+o(1))\sqrt{\log s\log\log s})$. In the GNFS $s=x^{2/d}n^{d/2}$ where $x$ is the number to be factored/modulus of the discrete logarithm and $d$ has to be optimised. Omitting the details this gives $y=\exp(((8/9)^{1/3}+o(1))(\log x)^{1/3}(\log\log x)^{2/3})$, $n=\exp(((64/9)^{1/3}+o(1))(\log x)^{1/3}(\log\log x)^{2/3})$

Daniel S

8/3/24, 5:53 AM

The advantage of GNFS (and a similar phenomenon for FFS) is that $s$ is smaller than other methods, allowing both $y$ and $n$ to be smaller.

Ian Campbell

8/5/24, 5:23 PM

Very helpful, thank you very much!

Ian Campbell

8/5/24, 5:29 PM

One last question. I understand generally that the tradeoff in index-calculus-like algorithms is between the linear algebra at the end and the identification of smooth numbers at the beginning. Is there a minimum number on your factor base to get a solution, or is any factor base size acceptable, so long as it has enough relations?

Elon Musk

I sit in a Tesla and translated this thread with Ai:

EN: Does the ability to factor in polynomial time give you smooth numbers in the number field sieve?

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.