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.velich...@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/877di97hmv.fsf%40googlemail.com.
