Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
add comment

Your Answer

 
discard

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

Browse other questions tagged or ask your own question.