Note that what makes this notable is that the time bound is proven (according to the paper, anyway). N^1/5 is much slower than we normally think of GNFS as being, but the thing to note is that GNFS isn't actually proven 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/understand an idea that is new to me.
This is an extremely well written paper. A high-school student with motivation could understand all of it in about 1 week of work.
The key idea here is in Lemma 3.3 which is a simplified presentation of Lehman's original idea. All of the "good" algorithms in this class are exploiting this observation.
Hittmeir adds a new ingredient, namely applying "baby-step-giant-step" searching. And Harvey makes a slightly better parameter choice and strategy than Hittmeir to get his result.
The new idea and value to me would be the concise explanation in Lemma 3.3.
A lot of the feedback is of the form, "who cares, since it doesn't push the state of the art in practical factoring", 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'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's over my head for 10 minutes reading though.
I'm a PhD student who studies stuff similar to this (I work in complexity theory), and one of my favorite "conversation starters" when I meet other researchers is whether they think integer factorization is actually a computationally difficult task.
Perhaps surprisingly, most people don'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't discovered an algorithm for it yet.