  Fast algorithms for arithmetic on real or complex polynomials are well-known
and have proven to be not only asymptotically efficient but also very
practical. Based on Fast Fourier Transform (FFT), they for instance multiply
two polynomials of degree up to N or multi-evaluate one at N points
simultaneously within quasi-linear time O(N.polylog N). An extension to (and in
fact the mere definition of) polynomials over the skew-field H of quaternions
is promising but still missing. The present work proposes three such
definitions which in the commutative case coincide but for H turn out to
differ, each one satisfying some desirable properties while lacking others. For
each notion we devise algorithms for according arithmetic; these are
quasi-optimal in that their running times match lower complexity bounds up to
polylogarithmic factors.
