Random binary invertible matrix

For implementation of McEliece cryptosystem, I'm trying to generate a random binary invertible matrix and its inverse. Because this is usually the most time-consuming part of generating a McEliece keypair (matrix size is usually around $2^{13}\times2^{13}$), I'm searching for ways to do it faster.

So far, I've tried to use following approaches:

• Generate an upper triangular matrix $U$ with random ones and zeroes in the upper triangle, and ones on diagonal (such $U$ is invertible), symmetrically generate $L$ lower triangular matrix, compute $M = UL$ and invert M by standard inversion. This is slow.
• Compute $M = UL$ and $M^{-1} = L^{-1}U^{-1}$. In this case, the inversion is a lot faster (there's no need to compute full row operations, as the inverse remains lower/upper triangular shape), but still slow.
• Have two identity matrices $I_1,I_2$, perform a number of random row operations on $I_1$, and symetrically perform those inverse row operations on $I_2$, so that equation $I_1^{-1} = I_2$ holds. I'm not sure what number of row operations should be done on the matrices so that the result would be completely random -- my best guess is that $n^2$ operations should be sufficient, giving algorithm complexity $O(n^3)$. If there was some lower limit so that the matrix would be random-enough, this approach could be the fastest.

Questions are:

• Is there some better algorithm, or is the $O(n^3)$ bound impossible to break?
• What is the lowest possible count of operations in the third algorithm so that the matrix gets undistinguishable from a random matrix from the first algorithm?

Thanks

-exa

-