I am working on cracking a hill cypher using modular linear algebra. Every example I have found online makes a big assumption that is not necessarily the case, and as I see it leaves a lot to be desired. It goes like this: You are working with an alphabet, say with 26 letters. You encode the cipher text as follows: c = Ap where c is a block of the cypher text, p is a corresponding block of the plaintext, and A is the encryption matrix. Skipping right to the point, lets say you have some general plaintext and cypher text, and you want to solve for A. Assuming that the key matrix is nxn, we can simply find n blocks of plaintext, and use them to form an nxn invertible matrix
P=[p_1|...|p_n]
and an associated (not necessarily invertible) matrix
C = [c_1|...|c_n]
So that we now have the system
C = AP
which we can of course solve by inverting P.
But here is the catch: we don't necessarily know that the columns of p are independent! In order to build a practical algorithm to solve this in the general case, we need to check each new block of plaintext p against the previous blocks to make sure it is linearly independent. Another way of saying this is that if we already have k blocks and we already have an nxk matrix
P* = [p_1|...|p_k]
we are looking to check if
P** = [p_1|...|p_k+1]
is full-rank. I have tried to figure out how to do this, but I can't seem to figure out a good algorithm to test it. I discovered by working out examples that you could test if two columns are independent exhaustively by simply multiplying one by succesively larger integers mod m. The result is a repeating pattern (the total number of possible vectors is finite), so this search will always be finite. But what is a less painful way of testing for linear independence/rank in modular matrix arithmetic?
Thanks in advance,
Paul