We propose a nearly optimal algorithm that uses 2n - 2 random parameters, O(n) memory space and O((nlog2n)loglogn) operations in a fixed arbitrary field in order to compute the rank and basis for the null space of a structured n x n matrix X represented with O(n) parameters of its short generator, as well as to solve a linear system Xy = b or to determine its in-consistency. If rank X = n, the algorithm also computes det X and a short generator of X -I. The cost bounds cover correctness verification for the output but not the cost of the generation of random parameters. The al- gorithm gives a unified treatment of various classes of structured matrices including ones of Toeplitz, Hankel, Vandermonde and Cauchy types.