  This paper presents the first decoding algorithm for Gabidulin codes over
Galois rings with provable quadratic complexity. The new method consists of two
steps: (1) solving a syndrome-based key equation to obtain the annihilator
polynomial of the error and therefore the column space of the error, (2)
solving a key equation based on the received word in order to reconstruct the
error vector. This two-step approach became necessary since standard solutions
as the Euclidean algorithm do not properly work over rings.
