ASKSAGE: Sage Q&A Forum - RSS feedhttps://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Mon, 27 Apr 2020 18:59:50 +0200RuntimeError Groebner basis for a Boolean systemhttps://ask.sagemath.org/question/51072/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.torresMon, 27 Apr 2020 18:59:50 +0200https://ask.sagemath.org/question/51072/Basis of invariant polynomial systemhttps://ask.sagemath.org/question/8509/basis-of-invariant-polynomial-system/I've been trying to compute a Grobner basis for a specific invariant polynomial system. It has 6 variables, 6 constants and 6 equations and is invariant to a group of cardinality 2. Various algorithms have been ran on it, including FGb/Gb through Maple and Singular through SAGE system. In both cases, the invariance was ignored and the computation of the Grobner basis failed to finish after hours (sometime days) of computation, while occupying all the memory available. Please note, I do not know what exactly the underlying algorithm was (Buchberger/F4/F5...).
It is an engineering application and in practice, I would only need the first few polynomials of the Grobner basis, that is the ones with as low degree as possible. I'm an engineer not a mathematician, so my knowledge of the topic is very limited. I did however understood, that in case of invariant systems, a SAGBI basis (or invariant Grobner basis) can be computed much more efficiently. More important, the invariant Grobner basis can be computed "up to a given degree", which is exactly what I probably need.
I got a hint that such algorithm might exist in SAGE. I've been searching through the SAGE documentation, but it seems I don't know what to search for and the system is huge.
If anyone can point me to right direction it would be great!
The problem:
X0 + Y0 - S0 = 0
X0 X1 + Y0 Y1 - S1 = 0
X0 ( X1^2 + 2 X2 )+ Y0 ( Y1^2 + 2 Y2 )- 2 S2 = 0
X0 ( X1^3 + 6 X2 X1 )+ Y0 ( Y1^3 + 6 Y2 Y1 ) - 6 S3 = 0
X0 ( X1^4 + 12 X2 X1^2 + 12 X2^2 )+ Y0 ( Y1^4 + 12 Y2 Y1^2 + 12 Y2^2 )- 24 S4 = 0
X0 ( X1^5 + 20 X2 X1^3 + 60 X2^2 X1 ) + Y0 ( Y1^5 + 20 Y2 Y1^3 + 60 Y2^2 Y1 ) - 120 S5 = 0
Where X0,X1,X2,Y0,Y1,Y2 are variables S0...S5 are constants, all are complex numbers.musevicThu, 24 Nov 2011 13:20:32 +0100https://ask.sagemath.org/question/8509/