Matrix Decrypt-Encrypt

A Hill cipher is a cipher based on matrix multiplication. To encrypt a message $\underline{c}$ of length $\leq 1 n \leq 4096$ in an alphabet of size $1 \leq l \leq 65535$, pick some key $A$ of size $n \times n$ and compute $\underline{c}_A = A\underline{c} \mod l$. To decrypt the message, apply $A^{-1}\underline{c}_A = (A^{-1}A)\underline{c} = I\underline{c} = \underline{c}$.

For this problem, given a message $\underline{c}_A$ (encrypted for $A$), the encryption key $A$, and the encryption key $B$, rekey the message $\underline{c}_A$ to become $\underline{c}_B$.

The input $c_A$ will be supplied in c. The final output $c_B$ must also be placed in c.

Input

• A - original encryption key.
• B - target encryption key.
• n - size of the Hill cipher key matrices.
• l - alphabet modulus.
• c - ciphertext encrypted under A, provided in place.

Output

• c - the input vector modified in place to become $\underline{c}_B$.