Polynomial Sequences

We call a finite list of polynomials a Polynomial Sequence.

Polynomial sequences in Sage can optionally be viewed as consisting of various parts or sub-sequences. These kind of polynomial sequences which naturally split into parts arise naturally for example in algebraic cryptanalysis of symmetric cryptographic primitives. The most prominent examples of these systems are: the small scale variants of the AES [CMR05] (cf. sage.crypto.mq.sr.SR()) and Flurry/Curry [BPW06]. By default, a polynomial sequence has exactly one part.

AUTHORS:

  • Martin Albrecht (2007ff): initial version
  • Martin Albrecht (2009): refactoring, clean-up, new functions
  • Martin Albrecht (2011): refactoring, moved to sage.rings.polynomial
  • Alex Raichev (2011-06): added algebraic_dependence()
  • Charles Bouillaguet (2013-1): added solve()

EXAMPLES:

As an example consider a small scale variant of the AES:

sage: sr = mq.SR(2,1,2,4,gf2=True,polybori=True)
sage: sr
SR(2,1,2,4)

We can construct a polynomial sequence for a random plaintext-ciphertext pair and study it:

sage: set_random_seed(1)
sage: F,s = sr.polynomial_system()
sage: F
Polynomial Sequence with 112 Polynomials in 64 Variables

sage: r2 = F.part(2); r2
(w200 + k100 + x100 + x102 + x103,
 w201 + k101 + x100 + x101 + x103 + 1,
 w202 + k102 + x100 + x101 + x102 + 1,
 w203 + k103 + x101 + x102 + x103,
 w210 + k110 + x110 + x112 + x113,
 w211 + k111 + x110 + x111 + x113 + 1,
 w212 + k112 + x110 + x111 + x112 + 1,
 w213 + k113 + x111 + x112 + x113,
 x100*w100 + x100*w103 + x101*w102 + x102*w101 + x103*w100,
 x100*w100 + x100*w101 + x101*w100 + x101*w103 + x102*w102 + x103*w101,
 x100*w101 + x100*w102 + x101*w100 + x101*w101 + x102*w100 + x102*w103 + x103*w102,
 x100*w100 + x100*w102 + x100*w103 + x101*w100 + x101*w101 + x102*w102 + x103*w100 + x100,
 x100*w101 + x100*w103 + x101*w101 + x101*w102 + x102*w100 + x102*w103 + x103*w101 + x101,
 x100*w100 + x100*w102 + x101*w100 + x101*w102 + x101*w103 + x102*w100 + x102*w101 + x103*w102 + x102,
 x100*w101 + x100*w102 + x101*w100 + x101*w103 + x102*w101 + x103*w103 + x103,
 x100*w100 + x100*w101 + x100*w103 + x101*w101 + x102*w100 + x102*w102 + x103*w100 + w100,
 x100*w102 + x101*w100 + x101*w101 + x101*w103 + x102*w101 + x103*w100 + x103*w102 + w101,
 x100*w100 + x100*w101 + x100*w102 + x101*w102 + x102*w100 + x102*w101 + x102*w103 + x103*w101 + w102,
 x100*w101 + x101*w100 + x101*w102 + x102*w100 + x103*w101 + x103*w103 + w103,
 x100*w102 + x101*w101 + x102*w100 + x103*w103 + 1,
 x110*w110 + x110*w113 + x111*w112 + x112*w111 + x113*w110,
 x110*w110 + x110*w111 + x111*w110 + x111*w113 + x112*w112 + x113*w111,
 x110*w111 + x110*w112 + x111*w110 + x111*w111 + x112*w110 + x112*w113 + x113*w112,
 x110*w110 + x110*w112 + x110*w113 + x111*w110 + x111*w111 + x112*w112 + x113*w110 + x110,
 x110*w111 + x110*w113 + x111*w111 + x111*w112 + x112*w110 + x112*w113 + x113*w111 + x111,
 x110*w110 + x110*w112 + x111*w110 + x111*w112 + x111*w113 + x112*w110 + x112*w111 + x113*w112 + x112,
 x110*w111 + x110*w112 + x111*w110 + x111*w113 + x112*w111 + x113*w113 + x113,
 x110*w110 + x110*w111 + x110*w113 + x111*w111 + x112*w110 + x112*w112 + x113*w110 + w110,
 x110*w112 + x111*w110 + x111*w111 + x111*w113 + x112*w111 + x113*w110 + x113*w112 + w111,
 x110*w110 + x110*w111 + x110*w112 + x111*w112 + x112*w110 + x112*w111 + x112*w113 + x113*w111 + w112,
 x110*w111 + x111*w110 + x111*w112 + x112*w110 + x113*w111 + x113*w113 + w113,
 x110*w112 + x111*w111 + x112*w110 + x113*w113 + 1)

We separate the system in independent subsystems:

sage: C = Sequence(r2).connected_components(); C
[[w213 + k113 + x111 + x112 + x113,
 w212 + k112 + x110 + x111 + x112 + 1,
 w211 + k111 + x110 + x111 + x113 + 1,
 w210 + k110 + x110 + x112 + x113,
 x110*w112 + x111*w111 + x112*w110 + x113*w113 + 1,
 x110*w112 + x111*w110 + x111*w111 + x111*w113 + x112*w111 + x113*w110 + x113*w112 + w111,
 x110*w111 + x111*w110 + x111*w112 + x112*w110 + x113*w111 + x113*w113 + w113,
 x110*w111 + x110*w113 + x111*w111 + x111*w112 + x112*w110 + x112*w113 + x113*w111 + x111,
 x110*w111 + x110*w112 + x111*w110 + x111*w113 + x112*w111 + x113*w113 + x113,
 x110*w111 + x110*w112 + x111*w110 + x111*w111 + x112*w110 + x112*w113 + x113*w112,
 x110*w110 + x110*w113 + x111*w112 + x112*w111 + x113*w110,
 x110*w110 + x110*w112 + x111*w110 + x111*w112 + x111*w113 + x112*w110 + x112*w111 + x113*w112 + x112,
 x110*w110 + x110*w112 + x110*w113 + x111*w110 + x111*w111 + x112*w112 + x113*w110 + x110,
 x110*w110 + x110*w111 + x111*w110 + x111*w113 + x112*w112 + x113*w111,
 x110*w110 + x110*w111 + x110*w113 + x111*w111 + x112*w110 + x112*w112 + x113*w110 + w110,
 x110*w110 + x110*w111 + x110*w112 + x111*w112 + x112*w110 + x112*w111 + x112*w113 + x113*w111 + w112],
[w203 + k103 + x101 + x102 + x103,
w202 + k102 + x100 + x101 + x102 + 1,
w201 + k101 + x100 + x101 + x103 + 1,
w200 + k100 + x100 + x102 + x103,
x100*w102 + x101*w101 + x102*w100 + x103*w103 + 1,
x100*w102 + x101*w100 + x101*w101 + x101*w103 + x102*w101 + x103*w100 + x103*w102 + w101,
x100*w101 + x101*w100 + x101*w102 + x102*w100 + x103*w101 + x103*w103 + w103,
x100*w101 + x100*w103 + x101*w101 + x101*w102 + x102*w100 + x102*w103 + x103*w101 + x101,
x100*w101 + x100*w102 + x101*w100 + x101*w103 + x102*w101 + x103*w103 + x103, x100*w101 + x100*w102 + x101*w100 + x101*w101 + x102*w100 + x102*w103 + x103*w102,
x100*w100 + x100*w103 + x101*w102 + x102*w101 + x103*w100,
x100*w100 + x100*w102 + x101*w100 + x101*w102 + x101*w103 + x102*w100 + x102*w101 + x103*w102 + x102,
x100*w100 + x100*w102 + x100*w103 + x101*w100 + x101*w101 + x102*w102 + x103*w100 + x100,
x100*w100 + x100*w101 + x101*w100 + x101*w103 + x102*w102 + x103*w101,
x100*w100 + x100*w101 + x100*w103 + x101*w101 + x102*w100 + x102*w102 + x103*w100 + w100,
x100*w100 + x100*w101 + x100*w102 + x101*w102 + x102*w100 + x102*w101 + x102*w103 + x103*w101 + w102]]
sage: C[0].groebner_basis()
Polynomial Sequence with 30 Polynomials in 16 Variables

and compute the coefficient matrix:

sage: A,v = Sequence(r2).coefficient_matrix()
sage: A.rank()
32

Using these building blocks we can implement a simple XL algorithm easily:

sage: sr = mq.SR(1,1,1,4, gf2=True, polybori=True, order='lex')
sage: F,s = sr.polynomial_system()

sage: monomials = [a*b for a in F.variables() for b in F.variables() if a<b]
sage: len(monomials)
190
sage: F2 = Sequence(map(mul, cartesian_product_iterator((monomials, F))))
sage: A,v = F2.coefficient_matrix(sparse=False)
sage: A.echelonize()
sage: A
6840 x 4474 dense matrix over Finite Field of size 2 (type 'print A.str()' to see all of the entries)
sage: A.rank()
4056
sage: A[4055]*v
(k001*k003)

TEST:

sage: P.<x,y> = PolynomialRing(QQ)
sage: I = [[x^2 + y^2], [x^2 - y^2]]
sage: F = Sequence(I, P)
sage: loads(dumps(F)) == F
True

Note

In many other computer algebra systems (cf. Singular) this class would be called Ideal but an ideal is a very distinct object from its generators and thus this is not an ideal in Sage.

[BPW06]J. Buchmann, A. Pychkine, R.-P. Weinmann Block Ciphers Sensitive to Groebner Basis Attacks in Topics in Cryptology – CT RSA‘06; LNCS 3860; pp. 313–331; Springer Verlag 2006; pre-print available at http://eprint.iacr.org/2005/200

Classes

sage.rings.polynomial.multi_polynomial_sequence.PolynomialSequence(arg1, arg2=None, immutable=False, cr=False, cr_str=None)

Construct a new polynomial sequence object.

INPUT:

  • arg1 - a multivariate polynomial ring, an ideal or a matrix
  • arg2 - an iterable object of parts or polynomials (default:None)
    • immutable - if True the sequence is immutable (default: False)
    • cr - print a line break after each element (default: False)
    • cr_str - print a line break after each element if ‘str’ is called (default: None)

EXAMPLES:

sage: P.<a,b,c,d> = PolynomialRing(GF(127),4)
sage: I = sage.rings.ideal.Katsura(P)

If a list of tuples is provided, those form the parts:

sage: F = Sequence([I.gens(),I.gens()], I.ring()); F # indirect doctest
[a + 2*b + 2*c + 2*d - 1,
 a^2 + 2*b^2 + 2*c^2 + 2*d^2 - a,
 2*a*b + 2*b*c + 2*c*d - b,
 b^2 + 2*a*c + 2*b*d - c,
 a + 2*b + 2*c + 2*d - 1,
 a^2 + 2*b^2 + 2*c^2 + 2*d^2 - a,
 2*a*b + 2*b*c + 2*c*d - b,
 b^2 + 2*a*c + 2*b*d - c]
sage: F.nparts()
2

If an ideal is provided, the generators are used:

sage: Sequence(I)
[a + 2*b + 2*c + 2*d - 1,
 a^2 + 2*b^2 + 2*c^2 + 2*d^2 - a,
 2*a*b + 2*b*c + 2*c*d - b,
 b^2 + 2*a*c + 2*b*d - c]

If a list of polynomials is provided, the system has only one part:

sage: F = Sequence(I.gens(), I.ring()); F
[a + 2*b + 2*c + 2*d - 1,
 a^2 + 2*b^2 + 2*c^2 + 2*d^2 - a,
 2*a*b + 2*b*c + 2*c*d - b,
 b^2 + 2*a*c + 2*b*d - c]
 sage: F.nparts()
 1
class sage.rings.polynomial.multi_polynomial_sequence.PolynomialSequence_generic(parts, ring, immutable=False, cr=False, cr_str=None)

Bases: sage.structure.sequence.Sequence_generic

Construct a new system of multivariate polynomials.

INPUT:

  • part - a list of lists with polynomials
  • ring - a multivariate polynomial ring
  • immutable - if True the sequence is immutable (default: False)
  • cr - print a line break after each element (default: False)
  • cr_str - print a line break after each element if ‘str’ is called (default: None)

EXAMPLES:

sage: P.<a,b,c,d> = PolynomialRing(GF(127),4)
sage: I = sage.rings.ideal.Katsura(P)

sage: Sequence([I.gens()], I.ring()) # indirect doctest
[a + 2*b + 2*c + 2*d - 1, a^2 + 2*b^2 + 2*c^2 + 2*d^2 - a, 2*a*b + 2*b*c + 2*c*d - b, b^2 + 2*a*c + 2*b*d - c]

If an ideal is provided, the generators are used.:

sage: Sequence(I)
[a + 2*b + 2*c + 2*d - 1, a^2 + 2*b^2 + 2*c^2 + 2*d^2 - a, 2*a*b + 2*b*c + 2*c*d - b, b^2 + 2*a*c + 2*b*d - c]

If a list of polynomials is provided, the system has only one part.:

sage: Sequence(I.gens(), I.ring())
[a + 2*b + 2*c + 2*d - 1, a^2 + 2*b^2 + 2*c^2 + 2*d^2 - a, 2*a*b + 2*b*c + 2*c*d - b, b^2 + 2*a*c + 2*b*d - c]
algebraic_dependence()

Returns the ideal of annihilating polynomials for the polynomials in self, if those polynomials are algebraically dependent. Otherwise, returns the zero ideal.

OUTPUT:

If the polynomials \(f_1,\ldots,f_r\) in self are algebraically dependent, then the output is the ideal \(\{F \in K[T_1,\ldots,T_r] : F(f_1,\ldots,f_r) = 0\}\) of annihilating polynomials of \(f_1,\ldots,f_r\). Here \(K\) is the coefficient ring of polynomial ring of \(f_1,\ldots,f_r\) and \(T_1,\ldots,T_r\) are new indeterminates. If \(f_1,\ldots,f_r\) are algebraically independent, then the output is the zero ideal in \(K[T_1,\ldots,T_r]\).

EXAMPLES:

sage: R.<x,y> = PolynomialRing(QQ)
sage: S = Sequence([x, x*y])
sage: I = S.algebraic_dependence(); I
Ideal (0) of Multivariate Polynomial Ring in T0, T1 over Rational Field
sage: R.<x,y> = PolynomialRing(QQ)
sage: S = Sequence([x, (x^2 + y^2 - 1)^2, x*y - 2])
sage: I = S.algebraic_dependence(); I
Ideal (16 + 32*T2 - 8*T0^2 + 24*T2^2 - 8*T0^2*T2 + 8*T2^3 + 9*T0^4 - 2*T0^2*T2^2 + T2^4 - T0^4*T1 + 8*T0^4*T2 - 2*T0^6 + 2*T0^4*T2^2 + T0^8) of Multivariate Polynomial Ring in T0, T1, T2 over Rational Field
sage: [F(S) for F in I.gens()]
[0]
sage: R.<x,y> = PolynomialRing(GF(7))
sage: S = Sequence([x, (x^2 + y^2 - 1)^2, x*y - 2])
sage: I = S.algebraic_dependence(); I
Ideal (2 - 3*T2 - T0^2 + 3*T2^2 - T0^2*T2 + T2^3 + 2*T0^4 - 2*T0^2*T2^2 + T2^4 - T0^4*T1 + T0^4*T2 - 2*T0^6 + 2*T0^4*T2^2 + T0^8) of Multivariate Polynomial Ring in T0, T1, T2 over Finite Field of size 7
sage: [F(S) for F in I.gens()]
[0]

Note

This function’s code also works for sequences of polynomials from a univariate polynomial ring, but i don’t know where in the Sage codebase to put it to use it to that effect.

AUTHORS:

  • Alex Raichev (2011-06-22)
coefficient_matrix(sparse=True)

Return tuple (A,v) where A is the coefficient matrix of this system and v the matching monomial vector.

Thus value of A[i,j] corresponds the coefficient of the monomial v[j] in the i-th polynomial in this system.

Monomials are order w.r.t. the term ordering of self.ring() in reverse order, i.e. such that the smallest entry comes last.

INPUT:

  • sparse - construct a sparse matrix (default: True)

EXAMPLE:

sage: P.<a,b,c,d> = PolynomialRing(GF(127),4)
sage: I = sage.rings.ideal.Katsura(P)
sage: I.gens()
[a + 2*b + 2*c + 2*d - 1,
 a^2 + 2*b^2 + 2*c^2 + 2*d^2 - a,
 2*a*b + 2*b*c + 2*c*d - b,
 b^2 + 2*a*c + 2*b*d - c]

sage: F = Sequence(I)
sage: A,v = F.coefficient_matrix()
sage: A
[  0   0   0   0   0   0   0   0   0   1   2   2   2 126]
[  1   0   2   0   0   2   0   0   2 126   0   0   0   0]
[  0   2   0   0   2   0   0   2   0   0 126   0   0   0]
[  0   0   1   2   0   0   2   0   0   0   0 126   0   0]

sage: v
[a^2]
[a*b]
[b^2]
[a*c]
[b*c]
[c^2]
[b*d]
[c*d]
[d^2]
[  a]
[  b]
[  c]
[  d]
[  1]

sage: A*v
[        a + 2*b + 2*c + 2*d - 1]
[a^2 + 2*b^2 + 2*c^2 + 2*d^2 - a]
[      2*a*b + 2*b*c + 2*c*d - b]
[        b^2 + 2*a*c + 2*b*d - c]
connected_components()

Split the polynomial system in systems which do not share any variables.

EXAMPLE:

As an example consider one part of AES, which naturally splits into four subsystems which are independent:

sage: sr = mq.SR(2,4,4,8,gf2=True,polybori=True)
sage: F,s = sr.polynomial_system()
sage: Fz = Sequence(F.part(2))
sage: Fz.connected_components()
[Polynomial Sequence with 128 Polynomials in 128 Variables,
 Polynomial Sequence with 128 Polynomials in 128 Variables,
 Polynomial Sequence with 128 Polynomials in 128 Variables,
 Polynomial Sequence with 128 Polynomials in 128 Variables]
connection_graph()

Return the graph which has the variables of this system as vertices and edges between two variables if they appear in the same polynomial.

EXAMPLE:

sage: B.<x,y,z> = BooleanPolynomialRing()
sage: F = Sequence([x*y + y + 1, z + 1])
sage: F.connection_graph()
Graph on 3 vertices
groebner_basis(*args, **kwargs)

Compute and return a Groebner basis for the ideal spanned by the polynomials in this system.

INPUT:

  • args - list of arguments passed to MPolynomialIdeal.groebner_basis call
  • kwargs - dictionary of arguments passed to MPolynomialIdeal.groebner_basis call

EXAMPLE:

sage: sr = mq.SR(allow_zero_inversions=True)
sage: F,s = sr.polynomial_system()
sage: gb = F.groebner_basis()
sage: Ideal(gb).basis_is_groebner()
True
ideal()

Return ideal spanned by the elements of this system.

EXAMPLE:

sage: sr = mq.SR(allow_zero_inversions=True)
sage: F,s = sr.polynomial_system()
sage: P = F.ring()
sage: I = F.ideal()
sage: I.elimination_ideal(P('s000*s001*s002*s003*w100*w101*w102*w103*x100*x101*x102*x103'))
Ideal (k002 + (a^3 + a + 1)*k003 + (a^2 + 1),
       k001 + (a^3)*k003, k000 + (a)*k003 + (a^2),
       k103 + k003 + (a^2 + a + 1),
       k102 + (a^3 + a + 1)*k003 + (a + 1),
       k101 + (a^3)*k003 + (a^2 + a + 1),
       k100 + (a)*k003 + (a),
       k003^2 + (a)*k003 + (a^2))
of Multivariate Polynomial Ring in k100, k101, k102, k103, x100, x101, x102, x103,
w100, w101, w102, w103, s000, s001, s002, s003, k000, k001, k002, k003 over Finite Field in a of size 2^4
monomials()

Return an unordered tuple of monomials in this polynomial system.

EXAMPLE:

sage: sr = mq.SR(allow_zero_inversions=True)
sage: F,s = sr.polynomial_system()
sage: len(F.monomials())
49
nmonomials()

Return the number of monomials present in this system.

EXAMPLE:

sage: sr = mq.SR(allow_zero_inversions=True)
sage: F,s = sr.polynomial_system()
sage: F.nmonomials()
49
nparts()

Return number of parts of this system.

EXAMPLE:

sage: sr = mq.SR(allow_zero_inversions=True)
sage: F,s = sr.polynomial_system()
sage: F.nparts()
4
nvariables()

Return number of variables present in this system.

EXAMPLE:

sage: sr = mq.SR(allow_zero_inversions=True)
sage: F,s = sr.polynomial_system()
sage: F.nvariables()
20
part(i)

Return i-th part of this system.

EXAMPLE:

sage: sr = mq.SR(allow_zero_inversions=True)
sage: F,s = sr.polynomial_system()
sage: R0 = F.part(1)
sage: R0
(k000^2 + k001, k001^2 + k002, k002^2 + k003, k003^2 + k000)
parts()

Return a tuple of parts of this system.

EXAMPLE:

sage: sr = mq.SR(allow_zero_inversions=True)
sage: F,s = sr.polynomial_system()
sage: l = F.parts()
sage: len(l)
4
ring()

Return the polynomial ring all elements live in.

EXAMPLE:

sage: sr = mq.SR(allow_zero_inversions=True,gf2=True,order='block')
sage: F,s = sr.polynomial_system()
sage: print F.ring().repr_long()
Polynomial Ring
 Base Ring : Finite Field of size 2
      Size : 20 Variables
  Block  0 : Ordering : deglex
             Names    : k100, k101, k102, k103, x100, x101, x102, x103, w100, w101, w102, w103, s000, s001, s002, s003
  Block  1 : Ordering : deglex
             Names    : k000, k001, k002, k003
subs(*args, **kwargs)

Substitute variables for every polynomial in this system and return a new system. See MPolynomial.subs for calling convention.

INPUT:

  • args - arguments to be passed to MPolynomial.subs
  • kwargs - keyword arguments to be passed to MPolynomial.subs

EXAMPLE:

sage: sr = mq.SR(allow_zero_inversions=True)
sage: F,s = sr.polynomial_system(); F
Polynomial Sequence with 40 Polynomials in 20 Variables
sage: F = F.subs(s); F
Polynomial Sequence with 40 Polynomials in 16 Variables
universe()

Return the polynomial ring all elements live in.

EXAMPLE:

sage: sr = mq.SR(allow_zero_inversions=True,gf2=True,order='block')
sage: F,s = sr.polynomial_system()
sage: print F.ring().repr_long()
Polynomial Ring
 Base Ring : Finite Field of size 2
      Size : 20 Variables
  Block  0 : Ordering : deglex
             Names    : k100, k101, k102, k103, x100, x101, x102, x103, w100, w101, w102, w103, s000, s001, s002, s003
  Block  1 : Ordering : deglex
             Names    : k000, k001, k002, k003
variables()

Return all variables present in this system. This tuple may or may not be equal to the generators of the ring of this system.

EXAMPLE:

sage: sr = mq.SR(allow_zero_inversions=True)
sage: F,s = sr.polynomial_system()
sage: F.variables()[:10]
(k003, k002, k001, k000, s003, s002, s001, s000, w103, w102)
class sage.rings.polynomial.multi_polynomial_sequence.PolynomialSequence_gf2(parts, ring, immutable=False, cr=False, cr_str=None)

Bases: sage.rings.polynomial.multi_polynomial_sequence.PolynomialSequence_generic

Polynomial Sequences over \(\mathbb{F}_2\).

eliminate_linear_variables(maxlength=+Infinity, skip=None, return_reductors=False)

Return a new system where linear leading variables are eliminated if the tail of the polynomial has length at most maxlength.

INPUT:

  • maxlength - an optional upper bound on the number of monomials by which a variable is replaced. If maxlength==+Infinity then no condition is checked. (default: +Infinity).
  • skip - an optional callable to skip eliminations. It must accept two parameters and return either True or False. The two parameters are the leading term and the tail of a polynomial (default: None).
  • return_reductors - if True the list of polynomials with linear leading terms which were used for reduction is also returned (default: False).

OUTPUT:

When return_reductors==True, then a pair of sequences of boolean polynomials are returned, along with the promises that:

  1. The union of the two sequences spans the same boolean ideal as the argument of the method
  2. The second sequence only contains linear polynomials, and it forms a reduced groebner basis (they all have pairwise distinct leading variables, and the leading variable of a polynomial does not occur anywhere in other polynomials).
  3. The leading variables of the second sequence do not occur anywhere in the first sequence (these variables have been eliminated).

When return_reductors==False, only the first sequence is returned.

EXAMPLE:

sage: B.<a,b,c,d> = BooleanPolynomialRing()
sage: F = Sequence([c + d + b + 1, a + c + d, a*b + c, b*c*d + c])
sage: F.eliminate_linear_variables() # everything vanishes
[]
sage: F.eliminate_linear_variables(maxlength=2)
[b + c + d + 1, b*c + b*d + c, b*c*d + c]
sage: F.eliminate_linear_variables(skip=lambda lm,tail: str(lm)=='a')
[a + c + d, a*c + a*d + a + c, c*d + c]

The list of reductors can be requested by setting ‘return_reductors’ to True:

sage: B.<a,b,c,d> = BooleanPolynomialRing()
sage: F = Sequence([a + b + d, a + b + c])
sage: F,R = F.eliminate_linear_variables(return_reductors=True)
sage: F
[]
sage: R
[a + b + d, c + d]

TESTS:

The function should really dispose of linear equations (trac ticket #13968):

sage: R.<x,y,z> = BooleanPolynomialRing()
sage: S = Sequence([x+y+z+1, y+z])
sage: S.eliminate_linear_variables(return_reductors=True)
([], [x + 1, y + z])

The function should take care of linear variables created by previous substitution of linear variables

sage: R.<x,y,z> = BooleanPolynomialRing()
sage: S = Sequence([x*y*z+x*y+z*y+x*z, x+y+z+1, x+y])
sage: S.eliminate_linear_variables(return_reductors=True)
([], [x + y, z + 1])

Note

This is called “massaging” in [CBJ07].

REFERENCES:

[CBJ07]Gregory V. Bard, and Nicolas T. Courtois, and Chris Jefferson. Efficient Methods for Conversion and Solution of Sparse Systems of Low-Degree Multivariate Polynomials over GF(2) via SAT-Solvers. Cryptology ePrint Archive: Report 2007/024. available at http://eprint.iacr.org/2007/024
solve(algorithm='polybori', n=1, eliminate_linear_variables=True, verbose=False, **kwds)

Find solutions of this boolean polynomial system.

This function provide a unified interface to several algorithms dedicated to solving systems of boolean equations. Depending on the particular nature of the system, some might be much faster than some others.

INPUT:

  • self - a sequence of boolean polynomials
  • algorithm - the method to use. Possible values are polybori, sat and exhaustive_search. (default: polybori, since it is always available)
  • n - number of solutions to return. If n == +Infinity then all solutions are returned. If \(n < \infty\) then \(n\) solutions are returned if the equations have at least \(n\) solutions. Otherwise, all the solutions are returned. (default: 1)
  • eliminate_linear_variables - whether to eliminate variables that appear linearly. This reduces the number of variables (makes solving faster a priori), but is likely to make the equations denser (may make solving slower depending on the method).
  • verbose - whether to display progress and (potentially) useful information while the computation runs. (default: False)

EXAMPLES:

Without argument, a single arbitrary solution is returned:

sage: R.<x,y,z> = BooleanPolynomialRing()
sage: S = Sequence([x*y+z, y*z+x, x+y+z+1])
sage: sol = S.solve(); sol                       # random
[{y: 1, z: 0, x: 0}]

We check that it is actually a solution:

sage: S.subs( sol[0] )
[0, 0, 0]

We obtain all solutions:

sage: sols = S.solve(n=Infinity); sols           # random
[{x: 0, y: 1, z: 0}, {x: 1, y: 1, z: 1}]
sage: map( lambda x: S.subs(x), sols)
[[0, 0, 0], [0, 0, 0]]

We can force the use of exhaustive search if the optional package FES is present:

sage: sol = S.solve(algorithm='exhaustive_search'); sol  # random, optional - FES
[{x: 1, y: 1, z: 1}]
sage: S.subs( sol[0] )
[0, 0, 0]

And we may use SAT-solvers if they are available:

sage: sol = S.solve(algorithm='sat'); sol                     # random, optional - CryptoMiniSat
[{y: 1, z: 0, x: 0}]
sage: S.subs( sol[0] )
[0, 0, 0]

TESTS:

Make sure that variables not occuring in the equations are no problem:

sage: R.<x,y,z,t> = BooleanPolynomialRing()
sage: S = Sequence([x*y+z, y*z+x, x+y+z+1])
sage: sols = S.solve(n=Infinity)
sage: map( lambda x: S.subs(x), sols)
[[0, 0, 0], [0, 0, 0], [0, 0, 0], [0, 0, 0]]

Not eliminating linear variables:

sage: sols = S.solve(n=Infinity, eliminate_linear_variables=False)
sage: map( lambda x: S.subs(x), sols)
[[0, 0, 0], [0, 0, 0], [0, 0, 0], [0, 0, 0]]

A tricky case where the linear equations are insatisfiable:

sage: R.<x,y,z> = BooleanPolynomialRing()
sage: S = Sequence([x*y*z+x*y+z*y+x*z, x+y+z+1, x+y+z])
sage: S.solve()
[]
class sage.rings.polynomial.multi_polynomial_sequence.PolynomialSequence_gf2e(parts, ring, immutable=False, cr=False, cr_str=None)

Bases: sage.rings.polynomial.multi_polynomial_sequence.PolynomialSequence_generic

PolynomialSequence over \(\mathbb{F}_{2^e}\), i.e extensions over GF(2).

weil_restriction()

Project this polynomial system to \(\mathbb{F}_2\).

That is, compute the Weil restriction of scalars for the variety corresponding to this polynomial system and express it as a polynomial system over \(\mathbb{F}_2\).

EXAMPLE:

sage: k.<a> = GF(2^2)
sage: P.<x,y> = PolynomialRing(k,2)
sage: a = P.base_ring().gen()
sage: F = Sequence([x*y + 1, a*x + 1], P)
sage: F2 = F.weil_restriction()
sage: F2
[x1*y0 + x0*y1 + x1*y1,
 x0*y0 + x1*y1 + 1,
 x0 + x1,
 x1 + 1,
 x0^2 + x0,
 x1^2 + x1,
 y0^2 + y0,
 y1^2 + y1]

Another bigger example for a small scale AES:

sage: sr = mq.SR(1,1,1,4,gf2=False)
sage: F,s = sr.polynomial_system(); F
Polynomial Sequence with 40 Polynomials in 20 Variables
sage: F2 = F.weil_restriction(); F2
Polynomial Sequence with 240 Polynomials in 80 Variables
sage.rings.polynomial.multi_polynomial_sequence.is_PolynomialSequence(F)

Return True if F is a PolynomialSequence.

INPUT:

  • F - anything

EXAMPLE:

sage: P.<x,y> = PolynomialRing(QQ)
sage: I = [[x^2 + y^2], [x^2 - y^2]]
sage: F = Sequence(I, P); F
[x^2 + y^2, x^2 - y^2]

sage: from sage.rings.polynomial.multi_polynomial_sequence import is_PolynomialSequence
sage: is_PolynomialSequence(F)
True

Table Of Contents

Previous topic

Ideals in multivariate polynomial rings.

Next topic

Multivariate Polynomials via libSINGULAR

This Page