So what I want to do is generating a (up to 1000 x 1000) invertible matrix over $\mathbb{Z}_2$. I did find some discussion (How do I generate a sparse invertible 10000 by 10000 binary matrix with 30 to 50 non-zeros per row?). However, if you generate from lower triangular matrix and apply permutation, what you get would be a matrix $A$ such that equation $Ax=b$ is easily solvable in $O(n^2)$ steps by substitution.
I want to generate a binary invertible matrix $A$ that is not-necessarily pick from $GL(\mathbb{Z}_2)$ but should be a "good" matrix, in the sense that its corresponding equation is not so easily broken, but easily constructed. By "easy" I mean the total steps required should not be far from $O(n^2)$. Is there a way to generate this kind of matrix?
---edit---
By "not-necessarily pick from $GL(\mathbb{Z}_2)$" I meant you could pick from a smaller class, for example unitary matrices $SU(\mathbb{Z}_2)$. This should be a random pick, though.