Ask Your Question

torres's profile - activity

2020-09-05 03:52:41 -0600 received badge  Teacher (source)
2020-09-04 03:30:55 -0600 answered a question Too long to compute the Groebner basis of a not so big system

Consider that there are many algorithms to compute a Groebner Base in Sage (by default you use std but there is also slimgb, etc...), and the efficiency of each one can differ by the monomial ordering you choose for your ring (in your case invlex): my suggestion is to try different combination of them, to see at least an improvement.

2020-04-28 05:37:20 -0600 received badge  Nice Question (source)
2020-04-27 17:04:15 -0600 received badge  Student (source)
2020-04-27 15:48:15 -0600 asked a question RuntimeError Groebner basis for a Boolean system

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.