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 <vesselin....@gmail.com> 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 <dim...@gmail.com> writes: > >> > Don't do Groebner bases over SR, use a proper polynomial ring. > >> > > >> > On Thu, Jul 1, 2021 at 4:56 PM Sam Ratcliffe > >> > <samuel.r...@hotmail.co.uk> 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/26238034-8a2f-4c4f-afe7-de9955538ce9n%40googlegroups.com.
