Ask Your Question

# 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

## 1 Answer

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

## Comments

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.

[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?

## Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

## Stats

Asked: 2021-01-19 17:21:56 +0200

Seen: 48 times

Last updated: Jan 19