# How to solve this system of equation in sage?

How to solve this system of equations in sage?

$x_1+l_1x_2+l_1^2x_3+\dots+l_1^{k-1}x_k=c_1+r$.

$x_1+l_2x_2+l_2^2x_3+\dots+l_2^{k-1}x_k=c_2+r^2$

$\dots$

$x_1+l_kx_2+l_k^2x_3+\dots+l_k^{k-1}x_k=c_k+r^k$

where $l_i$'s are different positive integers and $c_i,r$ are integers in $[0,256]$

In particular, we can solve with sage. Here is the code :

a0, a1,a2,b3,b4, b5,r,l1,l2,l3 = var('a0,a1,a2,b3,b4,b5, r,l1,l2,l3')

X=solve([a0+l1*a1+l1^2*a2==b3+r^3, a0+l2*a1+l2^2*a2==b4+r^2,a0+l3*a1+l3^2*a2==b5+r^1], a0,a1, a2)

edit retag close merge delete

k is supposed to be fixed ?

( 2019-01-10 19:57:16 +0100 )edit

Yes $k$ is fixed.

( 2019-01-10 20:29:31 +0100 )edit

Sort by ยป oldest newest most voted

Considering the notation of your first (general) example, simply copy the following code (as a script) and adjust $k$ as desired.

k = 3
r = var('r')
c = list(var('c%d' % i) for i in [1..k])
l = list(var('l%d' % i) for i in [1..k])
x = list(var('x%d' % i) for i in [1..k])
eqn_list = list(sum(x[i]*l[j]^i for i in range(k))==c[j]+r^(j+1) for j in range(k))
sol = solve(eqn_list,x)


Output of sol:

sage: sol
[[x1 == ((l1^2*l2 - l1*l2^2)*r^3 + (c3*l2 - c2*l3)*l1^2 - (l1^2*l3 - l1*l3^2)*r^2 + (l2^2*l3 - l2*l3^2)*c1 - (c3*l2^2 - c2*l3^2)*l1 + (l2^2*l3 - l2*l3^2)*r)/(l1^2*(l2 - l3) + l2^2*l3 - l2*l3^2 - (l2^2 - l3^2)*l1), x2 == -((l1^2 - l2^2)*r^3 - (c2 - c3)*l1^2 - c3*l2^2 + c2*l3^2 - (l1^2 - l3^2)*r^2 + (l2^2 - l3^2)*c1 + (l2^2 - l3^2)*r)/(l1^2*(l2 - l3) + l2^2*l3 - l2*l3^2 - (l2^2 - l3^2)*l1), x3 == ((l1 - l2)*r^3 - (l1 - l3)*r^2 - (c2 - c3)*l1 + c1*(l2 - l3) - c3*l2 + c2*l3 + (l2 - l3)*r)/(l1^2*(l2 - l3) + l2^2*l3 - l2*l3^2 - (l2^2 - l3^2)*l1)]]


An alternative way would be to go via a matrix (which is notably faster).

k = 3
r = var('r')
c = list(var('c%d' % i) for i in [1..k])
l = list(var('l%d' % i) for i in [1..k])
A = matrix(list(l[j]^i for i in range(k)) for j in range(k))
v = vector(c[j]+r^(j+1) for j in range(k))
sol = A\v


Output of sol:

sage: sol
((r^3 - c1 + c3 - (r^2 - c1 + c2 - r)*(l1 - l3)/(l1 - l2) - r)*(l1^2 - (l1^2 - l2^2)*l1/(l1 - l2))/(l1^2 - l3^2 - (l1^2 - l2^2)*(l1 - l3)/(l1 - l2)) + c1 + (r^2 - c1 + c2 - r)*l1/(l1 - l2) + r, (r^3 - c1 + c3 - (r^2 - c1 + c2 - r)*(l1 - l3)/(l1 - l2) - r)*(l1^2 - l2^2)/((l1^2 - l3^2 - (l1^2 - l2^2)*(l1 - l3)/(l1 - l2))*(l1 - l2)) - (r^2 - c1 + c2 - r)/(l1 - l2), -(r^3 - c1 + c3 - (r^2 - c1 + c2 - r)*(l1 - l3)/(l1 - l2) - r)/(l1^2 - l3^2 - (l1^2 - l2^2)*(l1 - l3)/(l1 - l2)))


This is indeed the same solution.

more