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

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

Sort by » oldest newest most voted

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).

more