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 directly and to extract a
>> solution from it “by hand”, i.e. there’s a bug.
>>
>> Indeed, the bug is unrelated to PolyBoRi:
>>
>> sage: R = PolynomialRing(GF(2), 36, "x", order="lex")
>> sage: I = Ideal([R.random_element(degree=1, terms=20) for _ in
>> range(36)])
>> sage: I.groebner_basis() # bombs out
>> 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)
>>
>> FWIW:
>>
>> sage: I.groebner_basis(algorithm="singular:std") # works as expected
>>
>>
>> Cheers,
>> Martin
>>
>> 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
>> >
