Is it surprising though? If you assume constant time when it doesn't exist (in this case arbitrary precision arithmetic), it should be obvious that you will be able to devise algorithms that are faster than the commonly accepted best results.

If you can do arithmetic on arbitrarily large integers in constant time, you can sort lists in linear time.