#10340: Strange error in groebner_basis()
----------------------------+-----------------------------------------------
Reporter: sbulygin | Owner: mvngu
Type: defect | Status: new
Priority: minor | Milestone:
Component: cryptography | Keywords: groebner_basis, Boolean Polynomials
Author: Stas Bulygin | Upstream: N/A
Reviewer: | Merged:
Work_issues: |
----------------------------+-----------------------------------------------
There is a ValueError occurring quite strangely when calling
groebner_basis() for an ideal in BooleanPolynomialRing. Here is the
example code
{{{
R.<Y0100, Y0101, Y0102, Y0103, Y0104, Y0105, Y0106, Y0107, Y0108, Y0109,
Y0110, Y0111, Y0112, Y0113, Y0114, Y0115, Y0116, Y0117, Y0118, Y0119,
Y0120, Y0121, Y0122, Y0123, Y0124, Y0125, Y0126, Y0127, Y0128, Y0129,
Y0130, Y0131, Y0132, Y0133, Y0134, Y0135, Y0136, Y0137, Y0138, Y0139,
Y0140, Y0141, Y0142, Y0143, Y0144, Y0145, Y0146, Y0147, X0100, X0101,
X0102, X0103, X0104, X0105, X0106, X0107, X0108, X0109, X0110, X0111,
X0112, X0113, X0114, X0115, X0116, X0117, X0118, X0119, X0120, X0121,
X0122, X0123, X0124, X0125, X0126, X0127, X0128, X0129, X0130, X0131,
X0132, X0133, X0134, X0135, X0136, X0137, X0138, X0139, X0140, X0141,
X0142, X0143, X0144, X0145, X0146, X0147, K00, K01, K02, K03, K04, K05,
K06, K07, K08, K09, K10, K11, K12, K13, K14, K15, K16, K17, K18, K19, K20,
K21, K22, K23, K24, K25, K26, K27, K28, K29, K30, K31, K32, K33, K34, K35,
K36, K37, K38, K39, K40, K41, K42, K43, K44, K45, K46,
K47>=BooleanPolynomialRing(order="degrevlex")
I=ideal([X0100 + K00 + 1,
X0101 + K01,
X0102 + K02 + 1,
X0103 + K03 + 1,
X0104 + K04,
X0105 + K05 + 1,
X0106 + K06,
X0107 + K07 + 1,
X0108 + K08,
X0109 + K09 + 1,
X0110 + K10 + 1,
X0111 + K11 + 1,
X0112 + K12 + 1,
X0113 + K13,
X0114 + K14 + 1,
X0115 + K15 + 1,
X0116 + K16 + 1,
X0117 + K17,
X0118 + K18,
X0119 + K19 + 1,
X0120 + K20 + 1,
X0121 + K21 + 1,
X0122 + K22 + 1,
X0123 + K23 + 1,
X0124 + K24 + 1,
X0125 + K25 + 1,
X0126 + K26,
X0127 + K27 + 1,
X0128 + K28,
X0129 + K29,
X0130 + K30,
X0131 + K31 + 1,
X0132 + K32 + 1,
X0133 + K33,
X0134 + K34,
X0135 + K35 + 1,
X0136 + K36,
X0137 + K37 + 1,
X0138 + K38 + 1,
X0139 + K39,
X0140 + K40 + 1,
X0141 + K41,
X0142 + K42 + 1,
X0143 + K43,
X0144 + K44,
X0145 + K45,
X0146 + K46,
X0147 + K47,
X0132 + 1,
X0116 + 1,
X0100,
X0133,
X0117 + 1,
X0101,
X0134,
X0118 + 1,
X0102 + 1,
X0135,
X0119,
X0103 + 1,
X0136 + 1,
X0120,
X0104,
X0137,
X0121 + 1,
X0105,
X0138,
X0122,
X0106 + 1,
X0139,
X0123,
X0107,
X0140 + 1,
X0124,
X0108 + 1,
X0141 + 1,
X0125 + 1,
X0109,
X0142,
X0126,
X0110,
X0143 + 1,
X0127 + 1,
X0111,
X0144 + 1,
X0128 + 1,
X0112,
X0145,
X0129,
X0113,
X0146 + 1,
X0130 + 1,
X0114 + 1,
X0147 + 1,
X0131 + 1,
X0115
])
I.groebner_basis() # reports an error
}}}
the error being
{{{
---------------------------------------------------------------------------
ValueError Traceback (most recent call
last)
/home/sbulygin/Sage/sage-4.6-linux-32bit-
ubuntu_10.04_lts-i686-Linux/<ipython console> in <module>()
/home/sbulygin/Sage/sage-4.6-linux-32bit-
ubuntu_10.04_lts-i686-Linux/local/lib/python2.6/site-
packages/sage/rings/polynomial/pbori.so in
sage.rings.polynomial.pbori.BooleanPolynomialIdeal.groebner_basis
(sage/rings/polynomial/pbori.cpp:25491)()
/home/sbulygin/Sage/sage-4.6-linux-32bit-
ubuntu_10.04_lts-i686-Linux/local/lib/python2.6/site-
packages/polybori/gbcore.pyc in wrapper(I, **kwds)
186
187 (I,state)=pre(**dict([(k,v) for (k,v) in
locals().iteritems() if k in pre_args]))
--> 188 I=f(I,**kwds)
189 if option_set:
190 if post:
/home/sbulygin/Sage/sage-4.6-linux-32bit-
ubuntu_10.04_lts-i686-Linux/local/lib/python2.6/site-
packages/polybori/gbcore.pyc in wrapper(I, **kwds)
186
187 (I,state)=pre(**dict([(k,v) for (k,v) in
locals().iteritems() if k in pre_args]))
--> 188 I=f(I,**kwds)
189 if option_set:
190 if post:
/home/sbulygin/Sage/sage-4.6-linux-32bit-
ubuntu_10.04_lts-i686-Linux/local/lib/python2.6/site-
packages/polybori/gbcore.pyc in __call__(self, *args, **kwds)
138 if heuristic:
139 complete_dict=self.heuristicFunction(complete_dict)
--> 140 return self.f(**complete_dict)
141 def __init__(self,f,heuristic_function):
142
(self.argnames,self.varargs,self.varopts,self.defaults)=getargspec(f)
/home/sbulygin/Sage/sage-4.6-linux-32bit-
ubuntu_10.04_lts-i686-Linux/local/lib/python2.6/site-
packages/polybori/gbcore.pyc in wrapper(I, **kwds)
186
187 (I,state)=pre(**dict([(k,v) for (k,v) in
locals().iteritems() if k in pre_args]))
--> 188 I=f(I,**kwds)
189 if option_set:
190 if post:
/home/sbulygin/Sage/sage-4.6-linux-32bit-
ubuntu_10.04_lts-i686-Linux/local/lib/python2.6/site-
packages/polybori/gbcore.pyc in __call__(self, *args, **kwds)
138 if heuristic:
139 complete_dict=self.heuristicFunction(complete_dict)
--> 140 return self.f(**complete_dict)
141 def __init__(self,f,heuristic_function):
142
(self.argnames,self.varargs,self.varopts,self.defaults)=getargspec(f)
/home/sbulygin/Sage/sage-4.6-linux-32bit-
ubuntu_10.04_lts-i686-Linux/local/lib/python2.6/site-
packages/polybori/gbcore.pyc in wrapper(I, **kwds)
186
187 (I,state)=pre(**dict([(k,v) for (k,v) in
locals().iteritems() if k in pre_args]))
--> 188 I=f(I,**kwds)
189 if option_set:
190 if post:
/home/sbulygin/Sage/sage-4.6-linux-32bit-
ubuntu_10.04_lts-i686-Linux/local/lib/python2.6/site-
packages/polybori/gbcore.pyc in wrapper(I, **kwds)
186
187 (I,state)=pre(**dict([(k,v) for (k,v) in
locals().iteritems() if k in pre_args]))
--> 188 I=f(I,**kwds)
189 if option_set:
190 if post:
/home/sbulygin/Sage/sage-4.6-linux-32bit-
ubuntu_10.04_lts-i686-Linux/local/lib/python2.6/site-
packages/polybori/gbcore.pyc in wrapper(I, **kwds)
186
187 (I,state)=pre(**dict([(k,v) for (k,v) in
locals().iteritems() if k in pre_args]))
--> 188 I=f(I,**kwds)
189 if option_set:
190 if post:
/home/sbulygin/Sage/sage-4.6-linux-32bit-
ubuntu_10.04_lts-i686-Linux/local/lib/python2.6/site-
packages/polybori/gbcore.pyc in wrapper(I, **kwds)
186
187 (I,state)=pre(**dict([(k,v) for (k,v) in
locals().iteritems() if k in pre_args]))
--> 188 I=f(I,**kwds)
189 if option_set:
190 if post:
/home/sbulygin/Sage/sage-4.6-linux-32bit-
ubuntu_10.04_lts-i686-Linux/local/lib/python2.6/site-
packages/polybori/gbcore.pyc in wrapper(I, **kwds)
185 print "preprocessing for option:", option
186
--> 187 (I,state)=pre(**dict([(k,v) for (k,v) in
locals().iteritems() if k in pre_args]))
188 I=f(I,**kwds)
189 if option_set:
/home/sbulygin/Sage/sage-4.6-linux-32bit-
ubuntu_10.04_lts-i686-Linux/local/lib/python2.6/site-
packages/polybori/gbcore.pyc in llfirst_pre(I, prot)
223
224 def llfirst_pre(I,prot):
--> 225 (eliminated,llnf, I)=eliminate(I,on_the_fly=False,prot=prot)
226 return (I,eliminated)
227
/home/sbulygin/Sage/sage-4.6-linux-32bit-
ubuntu_10.04_lts-i686-Linux/local/lib/python2.6/site-
packages/polybori/ll.pyc in eliminate(polys, on_the_fly, prot,
reduction_function, optimized)
109 reduction_function=reduction_function,
110 reduce_ll_system=(not on_the_fly),
--> 111 prot=prot)
112 else:
113 reductors=ll_encode(linear_leads,reduce=(not
on_the_fly),prot=prot)
/home/sbulygin/Sage/sage-4.6-linux-32bit-
ubuntu_10.04_lts-i686-Linux/local/lib/python2.6/site-
packages/polybori/ll.pyc in eliminate_ll_ranked(ll_system, to_reduce,
reduction_function, reduce_ll_system, prot)
146 return iter(Monomial(v).variables()).next().index()
147 #sorted_var_indices=[var_index(v) for v in sorted_vars]
--> 148 to_ring=Ring(len(sorted_vars))
149 map_back_indices = dict([(i, var_index(v)) for (i, v) in
enumerate(sorted_vars)])
150 map_from_indices = dict([(var_index(v), i) for (i, v) in
enumerate(sorted_vars)])
/home/sbulygin/Sage/sage-4.6-linux-32bit-
ubuntu_10.04_lts-i686-Linux/local/lib/python2.6/site-
packages/polybori/PyPolyBoRi.pyc in Ring(n, order)
17
18 def Ring(n, order='lp'):
---> 19 return BooleanPolynomialRing(n, 'x', order=order)
20
21 BoolePolynomialVector = BooleanPolynomialVector
/home/sbulygin/Sage/sage-4.6-linux-32bit-
ubuntu_10.04_lts-i686-Linux/local/lib/python2.6/site-
packages/sage/rings/polynomial/pbori.so in
sage.rings.polynomial.pbori.BooleanPolynomialRing.__init__
(sage/rings/polynomial/pbori.cpp:4458)()
ValueError: Number of variables must be greater than 1.
}}}
Interestingly enough, the same ideal, but without the last generator gets
through
{{{
I=ideal([X0100 + K00 + 1,
X0101 + K01,
X0102 + K02 + 1,
X0103 + K03 + 1,
X0104 + K04,
X0105 + K05 + 1,
X0106 + K06,
X0107 + K07 + 1,
X0108 + K08,
X0109 + K09 + 1,
X0110 + K10 + 1,
X0111 + K11 + 1,
X0112 + K12 + 1,
X0113 + K13,
X0114 + K14 + 1,
X0115 + K15 + 1,
X0116 + K16 + 1,
X0117 + K17,
X0118 + K18,
X0119 + K19 + 1,
X0120 + K20 + 1,
X0121 + K21 + 1,
X0122 + K22 + 1,
X0123 + K23 + 1,
X0124 + K24 + 1,
X0125 + K25 + 1,
X0126 + K26,
X0127 + K27 + 1,
X0128 + K28,
X0129 + K29,
X0130 + K30,
X0131 + K31 + 1,
X0132 + K32 + 1,
X0133 + K33,
X0134 + K34,
X0135 + K35 + 1,
X0136 + K36,
X0137 + K37 + 1,
X0138 + K38 + 1,
X0139 + K39,
X0140 + K40 + 1,
X0141 + K41,
X0142 + K42 + 1,
X0143 + K43,
X0144 + K44,
X0145 + K45,
X0146 + K46,
X0147 + K47,
X0132 + 1,
X0116 + 1,
X0100,
X0133,
X0117 + 1,
X0101,
X0134,
X0118 + 1,
X0102 + 1,
X0135,
X0119,
X0103 + 1,
X0136 + 1,
X0120,
X0104,
X0137,
X0121 + 1,
X0105,
X0138,
X0122,
X0106 + 1,
X0139,
X0123,
X0107,
X0140 + 1,
X0124,
X0108 + 1,
X0141 + 1,
X0125 + 1,
X0109,
X0142,
X0126,
X0110,
X0143 + 1,
X0127 + 1,
X0111,
X0144 + 1,
X0128 + 1,
X0112,
X0145,
X0129,
X0113,
X0146 + 1,
X0130 + 1,
X0114 + 1,
X0147 + 1,
X0131 + 1
])
I.groebner_basis() # works
}}}
the result being
{{{
[X0100, X0101, X0102 + 1, X0103 + 1, X0104, X0105, X0106 + 1, X0107, X0108
+ 1, X0109, X0110, X0111, X0112, X0113, X0114 + 1, X0115 + K15 + 1, X0116
+ 1, X0117 + 1, X0118 + 1, X0119, X0120, X0121 + 1, X0122, X0123, X0124,
X0125 + 1, X0126, X0127 + 1, X0128 + 1, X0129, X0130 + 1, X0131 + 1, X0132
+ 1, X0133, X0134, X0135, X0136 + 1, X0137, X0138, X0139, X0140 + 1, X0141
+ 1, X0142, X0143 + 1, X0144 + 1, X0145, X0146 + 1, X0147 + 1, K00 + 1,
K01, K02, K03, K04, K05 + 1, K06 + 1, K07 + 1, K08 + 1, K09 + 1, K10 + 1,
K11 + 1, K12 + 1, K13, K14, K16, K17 + 1, K18 + 1, K19 + 1, K20 + 1, K21,
K22 + 1, K23 + 1, K24 + 1, K25, K26, K27, K28 + 1, K29, K30 + 1, K31, K32,
K33, K34, K35 + 1, K36 + 1, K37 + 1, K38 + 1, K39, K40, K41 + 1, K42 + 1,
K43 + 1, K44 + 1, K45, K46 + 1, K47 + 1]
}}}
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/10340>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/sage-trac?hl=en.
