Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?



share|cite|improve this question

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.