Abstract. The classical and intensively studied problem of solving a Toeplitz/Hankel linear system of equations is omnipresent in computations in sciences, engineering and communication. Its equivalent formulations include computing polynomial gcd and lcm, Padé approximation, and Berlekamp-Massey's problem of recovering the linear recurrence coefficients. To improve the current record asymptotic bit operation cost of the solution, we rely on Hensel's $p$-adic lifting. We accelerate its recovery stage by exploiting randomization and the correlation between lifting and the computation of Smith's invariant factors of the input matrix. Furthermore, for the average input, the $2$-adic version of lifting is sufficient, allowing entire computation in binary form, which promises to be valuable for practical computations. Our resulting algorithms solve a nonsingular Toeplitz/Hankel linear system of $n$ equations by using $O(m(n) n \mu(\log \ n))$ bit operations (versus the information lower bound of the order of $n^2 \log \ n$), where $m(n)$ and $\mu(d)$ bound the arithmetic and Boolean cost of multiplying polynomials of degree $n$ and integers modulo $2^d +1$, respectively, and where the input coefficients are in $n^{O(1)}$. Our algorithms can be applied to a larger class of Toeplitz/Hankel-like linear systems.