Finished.
Not so easy 
And they are solutions with non invertible matrix
What?
They are invertible if you choose them correctly.
Off course,
If you choose them correctly.
This has been a fun puzzle so farā¦ my knowledge of linear algebra is over 30 years old and dusty.
Iām stuck with only being able to get the 2x2 hill challenges. My code times out for 3x3 or more. Iām brute force checking for hill values.
I have tried to compute this like AB mod 45 = C.
So, A = CBt(B Bt)i
My matrix classes only handle integersā¦ and when I compute (B Bt)i I get all 0 values. Perhaps this is because Iām not taking into account the āmod 45ā Do I need to scale up the matrix to avoid fractions? Do I need to make my matrix class handle doubles? (Iām in Java)
You have to compute the matrix inverse with a non-prime modulus.
Use GauĆ elimination.
Now Iām pre-computing a map of the modular inverse of all numbers from 0 to 44 for mod 45 in an initialization step. Almost half of the numbers donāt have modular inverses. Iām using this map to reduce the pivot to 1. My code works for the first test case, but not for the second.
The inverse that Iām trying to compute is of (B Bt).
Iām doing that because Iām solving like this: A = C Bt (B Bt)i Am I on the right track with this?
Whenever I multiply matrices together Iām doing mod 45 on it. Also, if an entire matrix has a greatest common factor, I reduce the matrix by that GCF.
For the second test case we have this B:
17, 30, 13, 36, 15, 21, 31
24, 23, 28, 24, 36, 24, 14
So, I have B Bt mod 45:
6, 24
24, 33
Thereās GCD of 3 so I reduce B Bt to:
2, 8
8, 11
But I canāt compute the inverse of this matrix because I hit on the problem of no modular inverse. Even if I swap the rows I have this problem. For example, when I make the first pivot 1 and then reduce the numbers below it to 0 I get:
1, 4
0, 24
But 24 does not have a modular inverse for us. I hit on the same problem even if I reverse the rows.
Am I barking up the wrong tree here? Thanks.
Read some earlier comments, same issue was discussed.
When you encounter a non-invertible pivot, you need to modify your matrix. There are matrix operations that make the next pivot invertible without modifying the solution.
I abandoned the approach of solving this: A = C Bt (B Bt)i
Iām solving for the hill matrix a different way - with square matrix subsets of B and C.
Decrypting is tricky because I need to invert the hill matrix but that is also working now.
All of the test cases in the puzzle are solved, however when I submit Iām at 93% with āAnother 6x6ā failing.
Not sure what to do because I canāt see the test inputs so I canāt diagnose where itās failing.
You can send me your code (in private), Iāll send back whatās wrong.