Ask Your Question

Solving symbolic equations to IntegerModRing(26)

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

klx gravatar image

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

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 flag offensive close merge delete

1 Answer

Sort by ยป oldest newest most voted

answered 2021-01-19 19:36:29 +0200

rburing gravatar image

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.

edit flag offensive delete link 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.

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

No automatic way form basis to eq.sub?

klx gravatar imageklx ( 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?

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

Your Answer

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

Add Answer

Question Tools

1 follower


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

Seen: 48 times

Last updated: Jan 19