Ask Your Question
0

Declare diagonal matrix with unknown variables in GF(2).

asked 2022-03-03 19:24:52 +0200

Katoptriss gravatar image

updated 2022-03-03 20:59:01 +0200

I have an equation of the form $AXB = V$, that I am trying to solve using Sage. All matrixes are in $GF(2)$, $A$ and $X$ are of size 32x32, and $B$ and $V$ column vectors of size 32.

My unknown matrix $X$ consists in zeros, except on the diagonal where I'd like to have 32 unknowns (representing each bit of a unknown 32-bits integer). I first tried to declare an array of variables like this:

vars_list = list(var("x_%d" % i) for i in range(32)) which throws me a "TypeError: x_0 is not a variable of Univariate Polynomial Ring in X over Finite Field of size 2 (using GF2X)". Looking at Sage documentation, I didn't find a way to declare them in $GF(2)$.

Using this link, I tried to declare my variables like this: x_1 = SR(GF(2)(1)) * var("x1") which gave me this time a "TypeError: positive characteristic not allowed in symbolic computations".

How should I setup $X$ so I can solve my equation?

edit retag flag offensive close merge delete

1 Answer

Sort by ยป oldest newest most voted
1

answered 2022-03-03 22:19:21 +0200

Emmanuel Charpentier gravatar image

updated 2022-03-03 22:41:34 +0200

A slight syntax error... Try :

sage: vars_list=[var("x_%d"%u) for u in range(32)]
sage: print(vars_list)
[x_0, x_1, x_2, x_3, x_4, x_5, x_6, x_7, x_8, x_9, x_10, x_11, x_12, x_13, x_14, x_15, x_16, x_17, x_18, x_19, x_20, x_21, x_22, x_23, x_24, x_25, x_26, x_27, x_28, x_29, x_30, x_31]

But SR (too) general methods for solving equations are highly inneficient in this case ; you should try to use Sage's methods for working on polynomials over GF(2). How ?

Simple :

sage: R1 = PolynomialRing(GF(2),32,"u") ; R1
Multivariate Polynomial Ring in u0, u1, u2, u3, u4, u5, u6, u7, u8, u9, u10, u11, u12, u13, u14, u15, u16, u17, u18, u19, u20, u21, u22, u23, u24, u25, u26, u27, u28, u29, u30, u31 over Finite Field of size 2
sage: X=diagonal_matrix(R1.gens()) ; print(X)
[ u0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0]
[  0  u1   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0]
[  0   0  u2   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0]
[  0   0   0  u3   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0]
[  0   0   0   0  u4   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0]
[  0   0   0   0   0  u5   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0]
[  0   0   0   0   0   0  u6   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0]
[  0   0   0   0   0   0   0  u7   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0]
[  0   0   0   0   0   0   0   0  u8   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0]
[  0   0   0   0   0   0   0   0   0  u9   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0]
[  0   0   0   0   0   0   0   0   0   0 u10   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0]
[  0   0   0   0   0   0   0   0   0   0   0 u11   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0]
[  0   0   0   0   0   0   0   0   0   0   0   0 u12   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0]
[  0   0   0   0   0   0   0   0   0   0   0   0   0 u13   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0]
[  0   0   0   0   0   0   0   0   0   0   0   0   0   0 u14   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0]
[  0   0   0   0   0   0   0   0   0   0   0   0   0   0   0 u15   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0]
[  0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0 u16   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0]
[  0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0 u17   0   0   0   0   0   0   0   0   0   0   0   0   0   0]
[  0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0 u18   0   0   0   0   0   0   0   0   0   0   0   0   0]
[  0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0 u19   0   0   0   0   0   0   0   0   0   0   0   0]
[  0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0 u20   0   0   0   0   0   0   0   0   0   0   0]
[  0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0 u21   0   0   0   0   0   0   0   0   0   0]
[  0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0 u22   0   0   0   0   0   0   0   0   0]
[  0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0 u23   0   0   0   0   0   0   0   0]
[  0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0 u24   0   0   0   0   0   0   0]
[  0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0 u25   0   0   0   0   0   0]
[  0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0 u26   0   0   0   0   0]
[  0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0 u27   0   0   0   0]
[  0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0 u28   0   0   0]
[  0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0 u29   0   0]
[  0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0 u30   0]
[  0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0 u31]

and work in R1 thereafter ; for example, Sys = R1(A)*X*R1(B)-R1(V) will give you a list of 32 polynomials describing your problem, and R1.ideal(Sys) will be a complete description of its solution...

I strongly recommend this book (freely available), whose chapter 9 (IIRC) will give you a nice overview of the possbilities of Sage, as well as the textbook this chapter points to.

HTH,

edit flag offensive delete link more

Comments

Thank you for the answer and the reference, I'll be sure to check it. A last question if I may: your answer worked fine, but it seems that if I declare a second matrix with a second set of 32 unknowns, operations like addition are impossible? I wanted to construct a small linear system with the unknowns being those 32x32 diagonal matrixes.

Katoptriss gravatar imageKatoptriss ( 2022-03-03 22:45:43 +0200 )edit

If I understand you correctly, you have 64 unknowns ; work in R1=PolynomialRing(GF(2), 64, "u"), setup your matrices as the upper-left and lower-right 32x32 matrices of uhe 64x64 iagonal matrix of your variables, and proceed accordingly...

Emmanuel Charpentier gravatar imageEmmanuel Charpentier ( 2022-03-03 22:56:15 +0200 )edit

Indeed, it wasn't very complex... Thank you for your help.

Katoptriss gravatar imageKatoptriss ( 2022-03-03 23:18:13 +0200 )edit

Suggestion: make the example more readable using 4 instead of 32.

slelievre gravatar imageslelievre ( 2022-03-04 16:59:12 +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

Stats

Asked: 2022-03-03 19:24:52 +0200

Seen: 49 times

Last updated: Mar 03