Efficient Generation of Random Nonsingular Matrices

Dana Randall

EECS Department, University of California, Berkeley

Technical Report No. UCB/CSD-91-658

, 1991

http://www2.eecs.berkeley.edu/Pubs/TechRpts/1991/CSD-91-658.pdf

We present an efficient algorithm for generating an n x n nonsingular matrix uniformly over a finite field. This algorithm is useful for several cryptographic and checking applications. Over GF[2] our algorithm runs in expected time M(n) + O(nsquared), where M(n) is the time needed to multiply two n x n matrices, and the expected number of random bits it uses is nsquared + 3. (Over other finite fields we use nsquared + O(1) random field elements on average.) This is more efficient than the standard method for solving this problem, both in terms of expected running time and the expected number of random bits used. The standard method is to generate random n x n matrices until we produce one with nonzero determinant. In contrast, our technique directly produces a random matrix guaranteed to have non-zero determinant. We also introduce efficient algorithms for related problems such as uniformly generating singular matrices or matrices with fixed determinant.

BibTeX citation:

@techreport{Randall:CSD-91-658,
    Author= {Randall, Dana},
    Title= {Efficient Generation of Random Nonsingular Matrices},
    Year= {1991},
    Month= {Nov},
    Url= {http://www2.eecs.berkeley.edu/Pubs/TechRpts/1991/6147.html},
    Number= {UCB/CSD-91-658},
    Abstract= {We present an efficient algorithm for generating an <i>n</i> x <i>n</i> nonsingular matrix uniformly over a finite field. This algorithm is useful for several cryptographic and checking applications. Over GF[2] our algorithm runs in expected time <i>M</i>(<i>n</i>) + <i>O</i>(<i>n</i>squared), where <i>M</i>(<i>n</i>) is the time needed to multiply two <i>n</i> x <i>n</i> matrices, and the expected number of random bits it uses is <i>n</i>squared + 3. (Over other finite fields we use <i>n</i>squared + <i>O</i>(1) random field elements on average.) This is more efficient than the standard method for solving this problem, both in terms of expected running time and the expected number of random bits used. The standard method is to generate random <i>n</i> x <i>n</i> matrices until we produce one with nonzero determinant. In contrast, our technique directly produces a random matrix guaranteed to have non-zero determinant. We also introduce efficient algorithms for related problems such as uniformly generating singular matrices or matrices with fixed determinant.},
}

EndNote citation:

%0 Report
%A Randall, Dana 
%T Efficient Generation of Random Nonsingular Matrices
%I EECS Department, University of California, Berkeley
%D 1991
%@ UCB/CSD-91-658
%U http://www2.eecs.berkeley.edu/Pubs/TechRpts/1991/6147.html
%F Randall:CSD-91-658