An exponent one-fifth algorithm for deterministic integer factorisation

I&#x27;m a PhD student who studies stuff similar to this (I work in complexity theory), and one of my favorite &quot;conversation starters&quot; when I meet other researchers is whether they think integer factorization is actually a computationally difficult task.<p>Perhaps surprisingly, most people don&#x27;t have strong feelings either way, and a good number of researchers suspect the task is actually efficiently computable (i.e., in polynomial-time). At least from the standpoint of complexity theory there are not really any compelling reasons to think factoring is hard, beyond the fact that we haven&#x27;t discovered an algorithm for it yet.

Note that what makes this notable is that the time bound is <i>proven</i> (according to the paper, anyway). N^1&#x2F;5 is much slower than we normally think of GNFS as being, but the thing to note is that GNFS isn&#x27;t actually <i>proven</i> to run that fast.

note, for people who were briefly confused like me, that to be considered polynomial time, it has to be polynomial in the number of bits, i.e. log(N).

I love a day when I see&#x2F;understand an idea that is new to me.<p>This is an extremely well written paper. A high-school student with motivation could understand all of it in about 1 week of work.<p>The key idea here is in Lemma 3.3 which is a simplified presentation of Lehman&#x27;s original idea. All of the &quot;good&quot; algorithms in this class are exploiting this observation.<p>Hittmeir adds a new ingredient, namely applying &quot;baby-step-giant-step&quot; searching. And Harvey makes a slightly better parameter choice and strategy than Hittmeir to get his result.<p>The new idea and value to me would be the concise explanation in Lemma 3.3.<p>A lot of the feedback is of the form, &quot;who cares, since it doesn&#x27;t push the state of the art in practical factoring&quot;, but for me, there is art in ideas like this. Lehman, Hittmeir and Harvey have put forth a really elegant and beautiful line of thought here---that is accessible!---and I hope you can enjoy it without too much worry about how much it is worth.

Does this have practical implications, as in, is this an algorithm that you&#x27;d run in practice, or is it mainly a theoretical bound due to constants hidden in the landau symbol?

Sounds like GNFS is still better if you believe its conjectured computational complexity, but this still seems like a good advance. Paper&#x27;s over my head for 10 minutes reading though.