Ask Your Question

RuntimeError Groebner basis for a Boolean system

asked 2020-04-27 18:59:50 +0200

torres gravatar image

Hello everyone,

i've started using sage for a few days and i'm having a rough time trying to use groebner basis with big boolean systems. Right now my goal is to verify the time it takes to solve these systems in this way: keep in mind that these equation are extracted from a cipher, and they are roughly 150 for 130 variables.

var = "x01, x02, x03, x04, x05, x06, x07, x08, x09, x10, x11, x12, x13, x14, x15, x16, x17, x18, x19, x20, x21, x22, x23, x24, x25, x26, x27, x28, x29, x30, x31, x32, x33, x34, x35, x36, x37, x38, x39, x40, x41, x42, x43, x44, x45, x46, x47, x49, x54, x70, x81, x89, x92, x93, y01, y02, y03, y04, y05, y06, y07, y08, y09, y10, y11, y12, y13, y14, y15, y16, y17, y18, y19, y20, y21, y22, y23, y24, y25, y26, y27, y28, y29, y30, y31, y32, y33, y34, y35, y36, y37, y38, y39, y40, y41, y42, y43, y44, y45, y46, y47, y48, y49, y50, y52, y80, y83, y84"

B = BooleanPolynomialRing(var)

System = [B('x93 + y84'), B('x92 +y83'), B('x89 + y80'), B('x54 + x81'), B('x49 + y52')]

I = ideal(System) 
G = I.groebner_basis()

The thing is that when i try to call the method 'variety' on the ideal 'I', i get a runtime error (even with this reduced example):

RuntimeError: error in Singular function call 'groebner':
int overflow in hilb 1
error occurred in or before standard.lib::stdhilb line 299: `    intvec hi = hilb( Id(1),1,W );`
expected intvec-expression. type 'help intvec;'
leaving standard.lib::stdhilb
leaving standard.lib::groebner

Do you have any idea why this happens? Or if you have any suggestions with the approach i could take, i'm happy to listen to them.

Thank you in advance for your time.

edit retag flag offensive close merge delete

1 Answer

Sort by ยป oldest newest most voted

answered 2020-04-30 16:41:47 +0200

rburing gravatar image

What is happening is: an ideal with generators $x_i^2 + x_i$ etc. plus your generators is created in the polynomial ring over GF(2) with lexicographic ordering, and a Groebner basis of this has to be computed, and for this Singular chooses an algorithm which doesn't work here. I think it's not easy to work around this on the SageMath level, so I reported it on the Singular trac.

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


Asked: 2020-04-27 18:59:50 +0200

Seen: 388 times

Last updated: Apr 27 '20