  A $\mathit{\text{moving frame}}$ at a rational curve is a basis of vectors
moving along the curve. When the rational curve is given parametrically by a
row vector $\mathbf{a}$ of univariate polynomials, a moving frame with
important algebraic properties can be defined by the columns of an invertible
polynomial matrix $P$, such that $\mathbf{a} P=[\gcd(\mathbf{a}),0\ldots,0]$. A
$\mathit{\text{degree-optimal moving frame}}$ has column-wise minimal degree,
where the degree of a column is defined to be the maximum of the degrees of its
components. Algebraic moving frames are closely related to the univariate
versions of the celebrated Quillen-Suslin problem, effective Nullstellensatz
problem, and syzygy module problem. However, this paper appears to be the first
devoted to finding an efficient algorithm for constructing a degree-optimal
moving frame, a property desirable in various applications. We compare our
algorithm with other possible approaches, based on already available
algorithms, and show that it is more efficient. We also establish several new
theoretical results concerning the degrees of an optimal moving frame and its
components. In addition, we show that any deterministic algorithm for computing
a degree-optimal algebraic moving frame can be augmented so that it assigns a
degree-optimal moving frame in a $GL_n(\mathbb{K})$-equivariant manner. This
crucial property of classical geometric moving frames, in combination with the
algebraic properties, can be exploited in various problems.
