[uqfblfih] Software complexity of the number field sieve

The number field sieve for factorization is reportedly quite hairy to implement.  However it provides absolute certainty at the end whether you've implemented it correctly: multiply the found factors.

I think very few difficult problems have this property.

In the worst case, a complicated SAT-solver does no better than a simple naive one.  This is true for all NP-complete problems.

Solve the linear system Ax=b in floating point and compute the residual Ax-b.  Is it not quite zero because that's the limit of floating point, or because there's a tiny bug in your implementation?  There's no absolute certainty.

There remains uncertainty that your GNFS sieve works correctly for all inputs, but for any given input, you can know.

Maybe lossless compression also has this property, though in the worst case scenario, compression is not possible.