Yiannis Moschovakis has been working on giving explicit lower bounds for algorithms deciding basic number theoretic questions. For example, together he and Lou van den Dries have shown that any algorithm deciding whether integers a,b are coprime must have infinitely many inputs on which the algorithm runs for more than log(log(a)) steps. See their paper "Is the Euclidean algorithm optimal among its peers?" at http://www.math.ucla.edu/~ynm/papers/acnote.ps The Euclidean algorithm requires logarithmic time, so their lower bound does not establish its optimality; this is discussed in the paper.

Here rather than using the number of steps a Turing machine runs as a gauge for the runtime of an algorithm they use the number of times certain primitives are called (like +,*,<,rem, and so forth). The proofs are done in a logical framework (using the language of model theory).