Ask Your Question
1

Subbing variables into equations not working when variables are from B.gen() function.

asked 2019-01-27 19:11:50 -0500

Stockfish3709 gravatar image

Hi, I'm working in a Boolean Polynomial Ring in 10 variables. The whole purpose of my project is to solve a system of equations.

As of now, I am working on an attack called the fixed XL attack. In summary, it involves guessing a value for one of the variables and then solving the system of equations. If it yields no answer, or if the values solved are not consistent with the system of equations, guess the other value for the variable and do it again. It has been shown that such a method could be faster than regular attacks.

So I have a problem with subbing in the values. The code below doesn't work. I get an error message KeyError: 'var_sub'.

NUMBER_OF_VARIABLES = 10
B = BooleanPolynomialRing(NUMBER_OF_VARIABLES,'x', order = 'degrevlex')
var_sub = B.gen(NUMBER_OF_VARIABLES -1)
print var_sub
>>> x9
B.inject_variables()
f = x0 + x1 + x7*x6*x9*x2*x0 + x6*x4*x3*x1 + x9*x7
print f.subs(var_sub = B(0))

I have no idea why it doesn't work though. I didn't get any answers from Google or documentation. It says that var_sub.parent() is stored as a Boolean Polynomial Ring, but even changing the third line of the code to var_sub = str(B.gen(NUMBER_OF_VARIABLES -1)) doesn't work.

On the other hand, simply just specifying what to sub in works. However, this is obviously not what I want as I do not want to keep specifying what to sub in when I increase the number of variables.

NUMBER_OF_VARIABLES = 10
B = BooleanPolynomialRing(NUMBER_OF_VARIABLES,'x', order = 'degrevlex')
B.inject_variables()
f = x0 + x1 + x7*x6*x9*x2*x0 + x6*x4*x3*x1 + x9*x7
print f.subs(x9 = B(0))
>>> x6*x4*x3*x1 + x0 + x1
edit retag flag offensive close merge delete

1 answer

Sort by ยป oldest newest most voted
1

answered 2019-01-28 01:37:29 -0500

slelievre gravatar image

Use a dictionary for substitutions.

The following should achieve the goal in the question.

sage: nvar = 10  # number of variables
sage: B = BooleanPolynomialRing(nvar, 'x', order='degrevlex')
sage: var = B.gens()
sage: var_sub = var[nvar - 1]
sage: var_sub
x9
sage: B.inject_variables()
sage: f = x0 + x1 + x7*x6*x9*x2*x0 + x6*x4*x3*x1 + x9*x7
sage: f.subs({var_sub: B.zero()})

Note that it prints out a deprecation warning about using order "degrevlex" with BooleanPolynomialRing.

DeprecationWarning: using 'degrevlex' in Boolean polynomial rings is deprecated.
If needed, reverse the order of variables manually and use 'degneglex'
See http://trac.sagemath.org/13849 for details.

Side comment: sing B.zero() is slightly neater (and faster) than using B(0).

edit flag offensive delete link more

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

Stats

Asked: 2019-01-27 19:11:50 -0500

Seen: 39 times

Last updated: Jan 28