Re: [sage-support] SR: RuntimeError: error in Singular function call 'groebner': int overflow in hilb 1
Hi Martin, I managed to circumvent the bug in the variety function for ideals for the GF(2) equation system generated by AES by using a sat solver. When generating an AES equation system over GF(2^e), I run into the same error using the variety function and was wondering if you knew any way around it? Thanks again for the help, Sam On Thursday, July 15, 2021 at 6:19:12 PM UTC+1 Sam Ratcliffe wrote: > Hi Martin, > > Thank you for the assistance! I am in the process of performing repeated > experiments in which I extract the key bits from the ideal/Groebner basis, > so reading off the solutions by hand is not ideal for repeated usage or the > scenarios in which there are fewer equations than variables and I can't > directly extract the key bits without solving for other variables too. I > tried to extract the generators from the ideal and construct a polynomial > sequence to solve and extract the key bits. I have tried doing this using > the solve() function for linear equations, but I can't seem to find a way > to specify that the solutions I am looking for are within GF(2). > > Additionally, I have run into problems with the groebner_basis() function. > For SR(i,1,1,4) the function seems to work correctly for all values of i. > However, when I change the array size to even SR(2,2,2,4) the > groebner_basis() function won't compute the Groebner basis of the > polynomial system, it runs for a while, and aborts with an error message. I > run the following: > > sage: sr = mq.SR(2,2,2,4,gf2=True,polybori=True,allow_zero_inversions=True) > sage: R = sr.ring().base_ring() > sage: P = sr.vector([R.random_element() for _ in range(sr.r*sr.c*sr.e)]) > sage: K = sr.vector([R.random_element() for _ in range(sr.r*sr.c*sr.e)]) > sage: C = sr(P, K) > sage: F, s = sr.polynomial_system(P=P, C=C) > sage: G = F.groebner_basis() > > And receive the following error: > > terminate called after throwing an instance of 'polybori::PBoRiError' > what(): Built-in matrix-size exceeded! > --- > RuntimeError Traceback (most recent call last) > in > > 1 G = F.groebner_basis() > > /opt/sagemath-9.2/local/lib/python3.7/site-packages/sage/rings/polynomial/multi_polynomial_sequence.py > > in groebner_basis(self, *args, **kwargs) > 534 [a, b, d] > 535 """ > --> 536 return self.ideal().groebner_basis(*args, **kwargs) > 537 > 538 def monomials(self): > > /opt/sagemath-9.2/local/lib/python3.7/site-packages/sage/rings/polynomial/pbori/pbori.pyx > > in sage.rings.polynomial.pbori.pbori.BooleanPolynomialIdeal.groebner_basis > (build/cythonized/sage/rings/polynomial/pbori/pbori.cpp:42313)() >5095 if "redsb" not in kwds: >5096 kwds["redsb"]=True > -> 5097 sig_on() >5098 gb = self._groebner_basis(**kwds) >5099 sig_off() > > RuntimeError: Aborted > > Any help with getting past this would be appreciated. > > Thanks again, > > Sam > > On Friday, July 2, 2021 at 8:48:14 AM UTC+1 vesselin@gmail.com wrote: > >> Thanks, Martin! >> >> > A workaround is to look at the linear equations directly and to extract >> a solution from it “by hand >> >> Oh, you mean he can directly look at the ideal and extract the solutions >> from there without having to compute the variety? >> >> For the particular SR(2,1,1,4) example the ideal would be >> >> sage: I >> Ideal (k200, k201, k202 + 1, k203, x200, x201 + 1, x202 + 1, x203, w200, >> w201 + 1, w202 + 1, w203 + 1, s100, s101, s102 + 1, s103 + 1, k100 + 1, >> k101 + 1, k102 + 1, k103, x100 + 1, x101 + 1, x102 + 1, x103 + 1, w100 + 1, >> w101, w102, w103, s000 + 1, s001 + 1, s002, s003, k000 + 1, k001, k002 + 1, >> k003) of Boolean PolynomialRing in k200, k201, k202, k203, x200, x201, >> x202, x203, w200, w201, w202, w203, s100, s101, s102, s103, k100, k101, >> k102, k103, x100, x101, x102, x103, w100, w101, w102, w103, s000, s001, >> s002, s003, k000, k001, k002, k003 >> >> The above are the linear equations you are referring to, right? >> >> Best, >> Vesselin >> >> On Friday, July 2, 2021 at 12:13:04 AM UTC+1 Martin Albrecht wrote: >> >>> Hi Vesselin, >>> >>> Sorry! Name-clash: Sage uses SR for the “Symbolic Ring” and we use >>> “mq.SR” for the small scale AES generator. This is what caused Dima’s >>> confusion, that’s all. >>> >>> A workaround is to look at the linear equations directl
Re: [sage-support] SR: RuntimeError: error in Singular function call 'groebner': int overflow in hilb 1
rtin
>>
>> Vesselin Velichkov writes:
>> > Hi Martin,
>> >
>> > Thank you for your reply!
>> >
>> > By "name clash" do you mean that both mq and BooleanPolynomialRing use
>> the
>> > same name i.e. "variety" for two different functions?
>> >
>> > Also, I didn't quite understand your solution -- the call to
>> > G.ideal().variety() from your first example still fails on my side with
>> the
>> > same overflow error. The call to I.variety() in the second example
>> succeeds
>> > though.
>> >
>> > Also, what do you mean by reading off the solution directly? How can
>> one do
>> > that?
>> >
>> > Thanks again!
>> >
>> > Best,
>> > Vesselin
>> >
>> > On Thursday, July 1, 2021 at 11:19:07 PM UTC+1 Martin Albrecht wrote:
>> >
>> >> Hi all,
>> >>
>> >> I think there’s a name clash here. mq.SR is a thing I wrote ages ago
>> for
>> >> producing systems of equations for small-scale variants of AES (not
>> the
>> >> symbolic ring).
>> >>
>> >> The problem comes from the variety() call and I think Sam did find a
>> bug:
>> >>
>> >> sage: sr = mq.SR(2,1,1,4, gf2=True, polybori=True,
>> >> allow_zero_inversions=True)
>> >> sage: P = sr.vector([0, 0, 1, 0])
>> >> sage: C = sr.vector([1, 0, 0, 0])
>> >> sage: F,s = sr.polynomial_system(P=P, C=C)
>> >> sage: G = F.groebner_basis() # this succeeds
>> >> sage: G.ideal().variety()
>> >>
>> >> More directly:
>> >>
>> >> sage: B = BooleanPolynomialRing(36, "x")
>> >> sage: I = Ideal([B.random_element(degree=1) for _ in range(36)])
>> >> sage: I.variety()
>> >>
>> >> RuntimeError: error in Singular function call 'groebner':
>> >> int overflow in hilb 1
>> >> error occurred in or before standard.lib::stdhilb line 300: ` intvec
>> hi =
>> >> hilb( Id[1],1,W );`
>> >> expected intvec-expression. type 'help intvec;'
>> >> leaving standard.lib::stdhilb (0)
>> >> leaving standard.lib::groebner (1104)
>> >>
>> >> @Sam: as a workaround, you can “read off” the solution directly.
>> >>
>> >> Cheers,
>> >> Martin
>> >>
>> >> Dima Pasechnik writes:
>> >> > Don't do Groebner bases over SR, use a proper polynomial ring.
>> >> >
>> >> > On Thu, Jul 1, 2021 at 4:56 PM Sam Ratcliffe
>> >> > wrote:
>> >> >>
>> >> >> I am using the SageMath implementation of SR and wish to recover
>> all
>> >> solutions to a polynomial system using the variety function for ideals
>> as
>> >> specified here:
>> >>
>> https://doc.sagemath.org/html/en/reference/cryptography/sage/crypto/mq/sr.html
>>
>> >> >>
>> >> >> When I run the following (as available on the above link):
>> >> >>
>> >> >> sage: sr = mq.SR(1,1,1,4, gf2=True, polybori=True)
>> >> >> sage: K = sr.base_ring()
>> >> >> sage: a = K.gen()
>> >> >> sage: K = [a]
>> >> >> sage: P = [1]
>> >> >> sage: F,s = sr.polynomial_system(P=P, K=K)
>> >> >> sage: I = F.ideal()
>> >> >> sage: for V in I.variety():
>> >> >> : for k,v in sorted(V.items()): : print("{} {}".format(k,
>> v))
>> >> : print("\n")
>> >> >>
>> >> >> --
>> >> >> You received this message because you are subscribed to the Google
>> >> Groups "sage-support" group.
>> >> >> To unsubscribe from this group and stop receiving emails from it,
>> send
>> >> an email to sage-support...@googlegroups.com.
>> >> >> To view this discussion on the web visit
>> >>
>> https://groups.google.com/d/msgid/sage-support/535596c4-8138-4894-b7c0-13293904ee30n%40googlegroups.com
>>
>> >> .
>> >>
>> >>
>> >> --
>> >>
>> >> _pgp: https://keybase.io/martinralbrecht
>> >> _www: https://malb.io
>> >> _prn: he/him or they/them
>> >>
>> >>
>>
>>
>> --
>>
>> _pgp: https://keybase.io/martinralbrecht
>> _www: https://malb.io
>> _prn: he/him or they/them
>>
>>
--
You received this message because you are subscribed to the Google Groups
"sage-support" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to sage-support+unsubscr...@googlegroups.com.
To view this discussion on the web visit
https://groups.google.com/d/msgid/sage-support/83cf75ff-47e4-4113-b97a-7416f6c64f50n%40googlegroups.com.
[sage-support] SR: RuntimeError: error in Singular function call 'groebner': int overflow in hilb 1
I am using SageMath's implementation of SR and encountered the above error
when trying to display the solutions to a polynomial system using the
variety function for ideals, as specified
here:
https://doc.sagemath.org/html/en/reference/cryptography/sage/crypto/mq/sr.html.
I am running SageMath 9.2 on Windows 10 with an Intel Core i5-6600K CPU @
3.50GHz, 3501 Mhz, 4 Core(s), 4 Logical Processor(s).
I use the following commands:
sage: sr = mq.SR(2,1,1,4, gf2=True, polybori=True,
allow_zero_inversions=True)
sage: K = sr.base_ring()
sage: a = K.gen()
sage: K = [a]
sage: P = [1]
sage: F,s = sr.polynomial_system(P=P, K=K)
sage: I = F.ideal()
sage: for V in I.variety():
: for k,v in sorted(V.items()):
: print("{} {}".format(k, v))
: print("\n")
This works only for SR(1,1,1,4) i.e. SR using only one round. If I even
increase the round number to 2 I encounter the following error:
RuntimeError: error in Singular function call 'groebner':
int overflow in hilb 1
error occurred in or before standard.lib::stdhilb line 350: ` i = std(i,
hi);`
leaving standard.lib::stdhilb
leaving standard.lib::groebner
Any help with this would be much appreciated, thank you.
The entire error message is much larger:
AttributeErrorTraceback (most recent call last)
/opt/sagemath-9.2/local/lib/python3.7/site-packages/sage/rings/polynomial/multi_polynomial_ideal.py
in dimension(self, singular)
1141 try:
-> 1142 return self.__dimension
1143 except AttributeError:
/opt/sagemath-9.2/local/lib/python3.7/site-packages/sage/structure/element.pyx
in sage.structure.element.Element.__getattr__
(build/cythonized/sage/structure/element.c:4703)()
492 """
--> 493 return self.getattr_from_category(name)
494
/opt/sagemath-9.2/local/lib/python3.7/site-packages/sage/structure/element.pyx
in sage.structure.element.Element.getattr_from_category
(build/cythonized/sage/structure/element.c:4815)()
505 cls = P._abstract_element_class
--> 506 return getattr_from_other_class(self, cls, name)
507
/opt/sagemath-9.2/local/lib/python3.7/site-packages/sage/cpython/getattr.pyx
in sage.cpython.getattr.getattr_from_other_class
(build/cythonized/sage/cpython/getattr.c:2619)()
371 dummy_error_message.name = name
--> 372 raise AttributeError(dummy_error_message)
373 attribute = attr
AttributeError: 'MPolynomialIdeal' object has no attribute '_cache__gens'
During handling of the above exception, another exception occurred:
KeyError Traceback (most recent call last)
/opt/sagemath-9.2/local/lib/python3.7/site-packages/sage/misc/cachefunc.pyx
in sage.misc.cachefunc.CachedMethodCaller.__call__
(build/cythonized/sage/misc/cachefunc.c:10304)()
1942 try:
-> 1943 return cache[k]
1944 except TypeError: # k is not hashable
KeyError: (('', None, None, False), ())
During handling of the above exception, another exception occurred:
RuntimeError Traceback (most recent call last)
RuntimeError: Error raised calling singular function
Exception ignored in:
'sage.libs.singular.function.LibraryCallHandler.handle_call'
RuntimeError: Error raised calling singular function
---
AttributeErrorTraceback (most recent call last)
/opt/sagemath-9.2/local/lib/python3.7/site-packages/sage/rings/polynomial/multi_polynomial_ideal.py
in dimension(self, singular)
1141 try:
-> 1142 return self.__dimension
1143 except AttributeError:
/opt/sagemath-9.2/local/lib/python3.7/site-packages/sage/structure/element.pyx
in sage.structure.element.Element.__getattr__
(build/cythonized/sage/structure/element.c:4703)()
492 """
--> 493 return self.getattr_from_category(name)
494
/opt/sagemath-9.2/local/lib/python3.7/site-packages/sage/structure/element.pyx
in sage.structure.element.Element.getattr_from_category
(build/cythonized/sage/structure/element.c:4815)()
505 cls = P._abstract_element_class
--> 506 return getattr_from_other_class(self, cls, name)
507
/opt/sagemath-9.2/local/lib/python3.7/site-packages/sage/cpython/getattr.pyx
in sage.cpython.getattr.getattr_from_other_class
(build/cythonized/sage/cpython/getattr.c:2619)()
371 dummy_error_message.name = name
--> 372 raise AttributeError(dummy_error_message)
373 attribute = attr
AttributeError: 'Singular' object has no attribute '_strip_prompt'
During handling of the above exception, another exception occurred:
KeyError Traceback (most recent call last)
/opt/sagemath-9.2/local/lib/python3.7/site-packages/sage/misc/cachefunc.pyx
in
[sage-support] SR: RuntimeError: error in Singular function call 'groebner': int overflow in hilb 1
I am using the SageMath implementation of SR and wish to recover all
solutions to a polynomial system using the variety function for ideals as
specified
here:
https://doc.sagemath.org/html/en/reference/cryptography/sage/crypto/mq/sr.html
When I run the following (as available on the above link):
sage: sr = mq.SR(1,1,1,4, gf2=True, polybori=True)
sage: K = sr.base_ring()
sage: a = K.gen()
sage: K = [a]
sage: P = [1]
sage: F,s = sr.polynomial_system(P=P, K=K)
sage: I = F.ideal()
sage: for V in I.variety():
: for k,v in sorted(V.items()): : print("{} {}".format(k, v)) :
print("\n")
--
You received this message because you are subscribed to the Google Groups
"sage-support" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to sage-support+unsubscr...@googlegroups.com.
To view this discussion on the web visit
https://groups.google.com/d/msgid/sage-support/535596c4-8138-4894-b7c0-13293904ee30n%40googlegroups.com.
