ASKSAGE: Sage Q&A Forum - Latest question feedhttp://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Mon, 28 Jan 2019 19:43:21 -0600Dividing Boolean Polynomials in Sage.http://ask.sagemath.org/question/45224/dividing-boolean-polynomials-in-sage/ Hi all,
I'm working in a Boolean Polynomial Ring. I have an equation generator. My objective is to divide the highest possible monomial by the leading monomial of my equations.
NUMBER_OF_VARIABLES = 15
B = BooleanPolynomialRing(NUMBER_OF_VARIABLES,'x', order = 'degrevlex')
Each equation that I generate looks something like this.
f = x6*x2*x1 + x6*x5*x4 + x9*x5*x4 + x9*x6*x0 + x10*x2*x1 + x10*x4*x1 + x11*x9*x7 + x11*x10*x0 + x12*x4*x0 + x12*x7*x3 + x12*x9*x0 + x12*x10*x3 + x12*x10*x5 + x13*x7*x0 + x13*x7*x5 + x13*x8*x6 + x13*x10*x9 + x13*x11*x2 + x14*x5*x4 + x14*x11*x5 + x14*x13*x12 + x6*x3 + x7*x2 + x9*x1 + x10*x9 + x14*x8 + x14*x13 + x3 + x7 + x8 + 1
Getting the leading monomial of f:
print f.lm()
>>> x6*x2*x1
Getting the highest possible monomial of my ring (15 variables)
print f.set().vars()
>>> x14*x13*x12*x11*x10*x9*x8*x7*x6*x5*x4*x3*x2*x1*x0
But somehow I get an error when I try to divide them.
f.set().vars()/f.lm()
>>> bad operand type for unary ~: 'sage.rings.polynomial.pbori.BooleanMonomial'
I checked the documentation and nothing seems to work. I have tried all of the methods below and they do not work.
f.set().vars().divide(f.lm())
# http://doc.sagemath.org/html/en/reference/polynomial_rings/sage/rings/polynomial/pbori.html
f.set().vars().reduce(Ideal([f.lm()]))
# https://stackoverflow.com/questions/35233406/multivariate-polynomial-division-in-sage
I'm really at a loss here. I've seen answers whereby the code `q,r = dividend.maxima_methods().divide(divisor)` is used, but this seems like such a simple thing to do. Surely I'm missing something out. Why isn't division working? Multiplication and addition works, so why shouldn't division work?
Stockfish3709Mon, 28 Jan 2019 19:43:21 -0600http://ask.sagemath.org/question/45224/Subbing variables into equations not working when variables are from B.gen() function.http://ask.sagemath.org/question/45216/subbing-variables-into-equations-not-working-when-variables-are-from-bgen-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
Stockfish3709Sun, 27 Jan 2019 19:11:50 -0600http://ask.sagemath.org/question/45216/Is there a way to make sage print out all monomials of a Boolean Ring?http://ask.sagemath.org/question/44921/is-there-a-way-to-make-sage-print-out-all-monomials-of-a-boolean-ring/Hi all,
In a finite ring, is there a way to get Sage to print out all possible monomials of the ring? I have a method, but it's very crude. It's simply doing something like taking a random variable to mutiply with a random ring element from B.random_element(). But this is obviously not what I want.
Below is the ring I'm working with.
B = BooleanPolynomialRing(20,'x', order = 'lex')
Is there a Sage function to put every monomial of the ring into a list? I can't seem to find it in Sage documentation.Stockfish3709Mon, 07 Jan 2019 02:55:20 -0600http://ask.sagemath.org/question/44921/Any way to make Sage display large matrices all in 1 line?http://ask.sagemath.org/question/44923/any-way-to-make-sage-display-large-matrices-all-in-1-line/Hi all,
Currently I have this code that generates large matrices.
B = BooleanPolynomialRing(25,'x', order = 'degneglex')
from sage.rings.polynomial.toy_variety import coefficient_matrix
from brial import *
v = BooleanPolynomialVector()
l = [B.random_element(degree = 3, terms = 4) for j in range(25)]
_ = [v.append(e) for e in l]
from sage.rings.polynomial.toy_variety import coefficient_matrix
print l
%time A, v = Sequence(l,B).coefficient_matrix()
print A
print v
The matrix generated is big, so big that it takes 2 lines to display all of it. It is hard to visualise. Is there some way of making each row of the matrix inline together such that they are not separated into different lines?Stockfish3709Mon, 07 Jan 2019 06:27:00 -0600http://ask.sagemath.org/question/44923/Sage not detecting intergers in Boolean Polynomial Ring?http://ask.sagemath.org/question/44880/sage-not-detecting-intergers-in-boolean-polynomial-ring/Hi all,
I'm trying to do a detecting system for terms in the equations used in a polynomial. I'm using Boolean Polynomials here.
Here's is my code. This prints all the terms of the equations.
P.<x,y,z> = BooleanPolynomialRing(3, order = 'lex')
equations = [x+y+z-1, y*z, x+z]
for i in range(len(equations)):
for j in equations[i]:
print j
Output:
x
y
z
1
y*z
x
z
As you can see, 1 appears in the output. However, when I implement this logic onto it, the output is empty.
for i in range(len(equations)):
for j in equations[i]:
if j == 1:
print 'true'
It's not like the logic doesn't work, if I change '1' to 'x', my logic works.
for i in range(len(equations)):
for j in equations[i]:
if j == x:
print 'true'
Output:
true
true
What am I doing wrong here?Stockfish3709Thu, 03 Jan 2019 22:54:41 -0600http://ask.sagemath.org/question/44880/How to convert boolean polynomials to DIMACS format?http://ask.sagemath.org/question/44885/how-to-convert-boolean-polynomials-to-dimacs-format/In sage, boolean polynomials can be solved by solvers supporting the DIMACS input. Can we convert boolean polynomials to DIMACS format using sage?
HridyaFri, 04 Jan 2019 03:29:14 -0600http://ask.sagemath.org/question/44885/Reduction In Quotient Rings (x^2 - x = 0)http://ask.sagemath.org/question/44514/reduction-in-quotient-rings-x2-x-0/Hi,
Thank you for taking the time to read this, it is very much appreciated.
My question concerns how to ensure that a polynomial within a quotient ring has the following property:
(x^2)k = 0
whereby x is any variable in the quotient ring and k is a positive integer.
This is the way I tried to go about the situation: I created a polynomial ring
P.<x,y,z,w> = PolynomialRing(GF(2), 4, order = 'degrevlex')
Since I am not working within a quotient ring, x^2 (or any of the other three variables) does not 'become' 0. Since I would like the property of x^2 = 0, I decided to create a quotient ring with some field equations:
Q = P.quotient_ring(ideal([var**q - var for var in P.gens()]))
whereby `q = P.base_ring.order()` .
However, when I then created the following polynomial, its parent was still P, so I changed its ring:
f1 = y*z + y*w + w^2
f1 = f1.change_ring(Q)
However, when I print f1, it, w^2 is still w^2 and has not reduced down to 0. I was wondering if I am missing something, please? This gets annoying because I am going to be working with Macaulay Matrices and hence, it is essential that I work within a quotient ring. Maybe I am missing some mathematics since this is all very new to me...
This is my sage input:
sage: P.<x,y,z,w> = PolynomialRing(GF(2), 4, order = 'degrevlex')
sage: q = P.base_ring().order()
sage: Q = P.quotient_ring(ideal([var**q - var for var in P.gens()]))
sage: f1 = y*z + y*w + w^2
sage: f1
y*z + y*w + w^2
sage: f1 = f1.change_ring(Q)
sage: f1
y*z + y*w + w^2
How would go about to ensure that w^2 = 0? I've already tried adding the original polynomial to the field equations when creating the quotient ring and changing its ring afterwards, like so:
sage: P.<x,y,z,w> = PolynomialRing(GF(2), 4, order = 'degrevlex')
sage: q = P.base_ring().order()
sage: f1 = y*z + y*w + w^2
sage: Q = P.quotient_ring(ideal([f1] + [var**q - var for var in P.gens()]))
sage: f1 = f1.change_ring(Q)
sage: f1
y*z + y*w + w^2
But as you can see, nothing happened...
Thank you!JoaoDDuarteThu, 29 Nov 2018 19:06:30 -0600http://ask.sagemath.org/question/44514/Finding the Groebner Basis of the following Ring. Is it possible? How could I make it work with multivariate polynomials?http://ask.sagemath.org/question/44409/finding-the-groebner-basis-of-the-following-ring-is-it-possible-how-could-i-make-it-work-with-multivariate-polynomials/ Hey guys,
I am trying to compute the groebner basis of a polynomial system that looks like this:
e = 48;
F.<r> = GF(2)[];
for p in F.polynomials(e):
if p.is_irreducible():
break;
R.<x> = PolynomialRing(GF(2),name="x").quotient(p)
I = Ideal([R.random_element(),R.random_element(),R.random_element(),R.random_element(),R.random_element(),R.random_element()])
print I.groebner_basis()
However I get an error: 'Ideal_pid' object has no attribute 'groebner_basis'
I am new to Sagemath so sorry if I misunderstand something. Also, how can I possibly make R to become a multivariate system by following the same structure, using an irreducible polynomial from GF(2) as presented in this code.
Thanks guys :)LujminaSat, 24 Nov 2018 08:08:46 -0600http://ask.sagemath.org/question/44409/In Boolean function truth tables in n variables, the table is arranged x_{n-1}, x_{n-2},...,x_1,x_0. How can I change so the order is x_0, x_1,... instead?http://ask.sagemath.org/question/43825/in-boolean-function-truth-tables-in-n-variables-the-table-is-arranged-x_n-1-x_n-2x_1x_0-how-can-i-change-so-the-order-is-x_0-x_1-instead/ In Boolean function truth tables in n variables, the table is arranged x_{n-1}, x_{n-2},...,x_1,x_0. How can I change so the order is x_0, x_1,... instead? twcTue, 02 Oct 2018 13:55:12 -0500http://ask.sagemath.org/question/43825/how to make an Macaulay matrix from polynoms over GF(2)http://ask.sagemath.org/question/39392/how-to-make-an-macaulay-matrix-from-polynoms-over-gf2/I have a `PolynomialRing(GF(2),'x1,x2,x3')` and over it two polynomials `x1*x2 + x1*x3 + x1`, `x1+x2+1` and I would like to rewrite it in Macaulay matrix in order `x1x1`, `x1x2`, `x2x2`, `x1x3`, `x2x3`, `x3x3`,`x1`,`x2`,`x3`, absolute term
so it should be
0 1 0 1 0 0 1 0 0 0
0 0 0 0 0 0 1 1 0 1
Is there something in sage ?RomiSun, 05 Nov 2017 06:57:50 -0600http://ask.sagemath.org/question/39392/Memory leak when doing ANF of boolean functions?http://ask.sagemath.org/question/35623/memory-leak-when-doing-anf-of-boolean-functions/I am using SageMath version 7.2 (EDIT: I confirm the same behavior under Sage version 7.4)
sage: B = random_boolean_function(3)
sage: get_memory_usage()
732.5078125
sage: B.algebraic_normal_form()
x0*x1*x2 + x0*x1 + x0 + x2
sage: get_memory_usage()
743.53125
sage: B.algebraic_normal_form()
x0*x1*x2 + x0*x1 + x0 + x2
sage: get_memory_usage()
749.04296875
sage: B.algebraic_normal_form()
x0*x1*x2 + x0*x1 + x0 + x2
sage: get_memory_usage()
754.6875
sage: B.algebraic_normal_form()
x0*x1*x2 + x0*x1 + x0 + x2
sage: get_memory_usage()
760.19921875
After each ANF call the memory used is **rising**. Is this a memory leak?sageuser1Thu, 17 Nov 2016 02:50:56 -0600http://ask.sagemath.org/question/35623/About Boolean Functionhttp://ask.sagemath.org/question/35258/about-boolean-function/I want to find the Algebraic Normal Form of a boolean function.
For example:
sage: R.<x1,x2,x3> = BooleanPolynomialRing(3, order='degneglex')
sage: x3>x1
True
sage: L = BooleanFunction(x1+x2*x3)
sage: L.truth_table()
(False, True, False, True, False, True, True, False)
sage: L.algebraic_normal_form()
x0 + x1*x2
Unfortunately, Algebraic Normal Form of this specific boolean function is not correct (x0 should be x3, x1 should be x2 and x2 should be x1). The answer of the ANF() method is in order='lex' (not as I desired in order = 'degneglex'). Furthermore, the ANF() form is calculated out of this ring (x0 involved?)
How should I extract the ANF() in correct syntax (where x3>x2>x1)?sageuser1Wed, 26 Oct 2016 06:29:16 -0500http://ask.sagemath.org/question/35258/subs() function gives KeyError when keyword is a list memberhttp://ask.sagemath.org/question/32426/subs-function-gives-keyerror-when-keyword-is-a-list-member/ I have a multivariate Boolean polynomial my_poly in xi (x0,x1,...,etc) and want to substitute one of the variables (say e.g. x0=0). my_poly subs(x0=0) works but I need to determine the exact variable (left hand side of '=') and value (right hand side of '=') at run-time depending on some conditions. The problem is subs() function do not accept expression on the left hand side of '=' and I have many xi variables, so if else is not practical. How can I solve this issue?adnanbaysalWed, 03 Feb 2016 03:25:06 -0600http://ask.sagemath.org/question/32426/