Lower bounds for solving linear diophantine equations on random access machines
F. Meyer auf der Heide, Journal of the ACM (JACM) (1985) 929–937.