# Solving symbolic equations to IntegerModRing(26)

To solve the Hill Cipher a have setup symbolic equations;

R = IntegerModRing(26)
a,b,c,d,x1,x2 = var('k_1,k_2,k_3,k_4,x1,x2')
K = Matrix(SR,[[a,b],[c,d]]); K
print(K)

pl = vector(SR,[1,29])
ci = vector(SR,[8,21])
eq1,eq2 = (K*pl-ci)

pl = vector(SR,[25,22])
ci = vector(SR,[x1,i])
eq3,eq4 = (K*pl-ci)

pl = vector(SR,[7,16])
ci = vector(SR,[x2,19])
eq5,eq6 = (K*pl-ci)

solve((eq1,eq2,eq3,eq4,eq5,eq6), [a,b,c,d,x1,x2])


There is a problem that The symbolic equations are not working modulo 26. For example, the first equation is

k_1 + 29*k_2 - 8


So how can I properly turn them into modulo 26 and solve the equations in modulo 26?

edit retag close merge delete

Sort by » oldest newest most voted

You can define a polynomial ring over $\mathbb{Z}/26\mathbb{Z}$ with an ideal in it generated by (the left-hand sides of) your equations, and calculate a Groebner basis of it with respect to a lexicographic monomial ordering. This will "triangularize" the system of equations, and if you are lucky you can solve it by successive substitutions. Here is the setup:

R = PolynomialRing(IntegerModRing(26), names='k_1,k_2,k_3,k_4,x1,x2', order='lex')
a,b,c,d,x1,x2 = R.gens()
K = Matrix(R,[[a,b],[c,d]]); K

pl = vector(R,[1,29])
ci = vector(R,[8,21])
eq1,eq2 = (K*pl-ci)

pl = vector(R,[25,22])
ci = vector(R,[x1,-5])
eq3,eq4 = (K*pl-ci)

pl = vector(R,[7,16])
ci = vector(R,[x2,19])
eq5,eq6 = (K*pl-ci)

I = R.ideal([eq1,eq2,eq3,eq4,eq5,eq6])


I replaced $i$ by $-5$ because it will lead to a solution; the other option, i.e. $5$, doesn't.

sage: I.groebner_basis()
[k_1 + 15*x2 + 10, k_2 + 21*x2 + 20, k_3 + 9, k_4 + 16, x1 + 5*x2 + 14]


This can be viewed as a list of equations (set equal to zero). Each of these equations can be solved by putting its first term to the other side (so only x2 remains as an indeterminate). Indeed:

sage: [eq.subs(x1=-5*x2-14,k_4=-16,k_3=-9,k_2=-21*x2-20,k_1=-15*x2-10) for eq in [eq1,eq2,eq3,eq4,eq5,eq6]]
[0, 0, 0, 0, 0, 0]


The system of equations with $i$ replaced by $5$ is unsolvable because the Groebner basis contains the constant $2$, or, if you prefer: because 12*eq2 + 5*eq4 - eq6 evaluates to $2$ in that case.

more

Sorry, $i$ was a typo that takes your time. Is this the only way? I was expecting that the symbolic package can try solve by Gaussian Elimination.

( 2021-01-19 20:10:04 +0200 )edit

No automatic way form basis to eq.sub?

( 2021-01-19 20:24:05 +0200 )edit

[k_1 + 11x2, k_2 + 11x2, k_3, k_4 + 1, x1 + 23*x2, 2]. I've got this as an experiment, what is the value of k_3 and the last 2?

( 2021-01-19 20:28:01 +0200 )edit