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:
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,
w100*x100 + w100*x103 + w101*x102 + w102*x101 + w103*x100,
w100*x100 + w100*x101 + w101*x100 + w101*x103 + w102*x102 + w103*x101,
w100*x101 + w100*x102 + w101*x100 + w101*x101 + w102*x100 + w102*x103 + w103*x102,
w100*x100 + w100*x101 + w100*x103 + w101*x101 + w102*x100 + w102*x102 + w103*x100 + x100,
w100*x102 + w101*x100 + w101*x101 + w101*x103 + w102*x101 + w103*x100 + w103*x102 + x101,
w100*x100 + w100*x101 + w100*x102 + w101*x102 + w102*x100 + w102*x101 + w102*x103 + w103*x101 + x102,
w100*x101 + w101*x100 + w101*x102 + w102*x100 + w103*x101 + w103*x103 + x103,
w100*x100 + w100*x102 + w100*x103 + w101*x100 + w101*x101 + w102*x102 + w103*x100 + w100,
w100*x101 + w100*x103 + w101*x101 + w101*x102 + w102*x100 + w102*x103 + w103*x101 + w101,
w100*x100 + w100*x102 + w101*x100 + w101*x102 + w101*x103 + w102*x100 + w102*x101 + w103*x102 + w102,
w100*x101 + w100*x102 + w101*x100 + w101*x103 + w102*x101 + w103*x103 + w103,
w100*x102 + w101*x101 + w102*x100 + w103*x103 + 1,
w110*x110 + w110*x113 + w111*x112 + w112*x111 + w113*x110,
w110*x110 + w110*x111 + w111*x110 + w111*x113 + w112*x112 + w113*x111,
w110*x111 + w110*x112 + w111*x110 + w111*x111 + w112*x110 + w112*x113 + w113*x112,
w110*x110 + w110*x111 + w110*x113 + w111*x111 + w112*x110 + w112*x112 + w113*x110 + x110,
w110*x112 + w111*x110 + w111*x111 + w111*x113 + w112*x111 + w113*x110 + w113*x112 + x111,
w110*x110 + w110*x111 + w110*x112 + w111*x112 + w112*x110 + w112*x111 + w112*x113 + w113*x111 + x112,
w110*x111 + w111*x110 + w111*x112 + w112*x110 + w113*x111 + w113*x113 + x113,
w110*x110 + w110*x112 + w110*x113 + w111*x110 + w111*x111 + w112*x112 + w113*x110 + w110,
w110*x111 + w110*x113 + w111*x111 + w111*x112 + w112*x110 + w112*x113 + w113*x111 + w111,
w110*x110 + w110*x112 + w111*x110 + w111*x112 + w111*x113 + w112*x110 + w112*x111 + w113*x112 + w112,
w110*x111 + w110*x112 + w111*x110 + w111*x113 + w112*x111 + w113*x113 + w113,
w110*x112 + w111*x111 + w112*x110 + w113*x113 + 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,
w110*x112 + w111*x111 + w112*x110 + w113*x113 + 1,
w110*x112 + w111*x110 + w111*x111 + w111*x113 + w112*x111 + w113*x110 + w113*x112 + x111,
w110*x111 + w111*x110 + w111*x112 + w112*x110 + w113*x111 + w113*x113 + x113,
w110*x111 + w110*x113 + w111*x111 + w111*x112 + w112*x110 + w112*x113 + w113*x111 + w111,
w110*x111 + w110*x112 + w111*x110 + w111*x113 + w112*x111 + w113*x113 + w113,
w110*x111 + w110*x112 + w111*x110 + w111*x111 + w112*x110 + w112*x113 + w113*x112,
w110*x110 + w110*x113 + w111*x112 + w112*x111 + w113*x110,
w110*x110 + w110*x112 + w111*x110 + w111*x112 + w111*x113 + w112*x110 + w112*x111 + w113*x112 + w112,
w110*x110 + w110*x112 + w110*x113 + w111*x110 + w111*x111 + w112*x112 + w113*x110 + w110,
w110*x110 + w110*x111 + w111*x110 + w111*x113 + w112*x112 + w113*x111,
w110*x110 + w110*x111 + w110*x113 + w111*x111 + w112*x110 + w112*x112 + w113*x110 + x110,
w110*x110 + w110*x111 + w110*x112 + w111*x112 + w112*x110 + w112*x111 + w112*x113 + w113*x111 + x112],
[w203 + k103 + x101 + x102 + x103,
w202 + k102 + x100 + x101 + x102 + 1,
w201 + k101 + x100 + x101 + x103 + 1,
w200 + k100 + x100 + x102 + x103,
w100*x102 + w101*x101 + w102*x100 + w103*x103 + 1,
w100*x102 + w101*x100 + w101*x101 + w101*x103 + w102*x101 + w103*x100 + w103*x102 + x101,
w100*x101 + w101*x100 + w101*x102 + w102*x100 + w103*x101 + w103*x103 + x103,
w100*x101 + w100*x103 + w101*x101 + w101*x102 + w102*x100 + w102*x103 + w103*x101 + w101,
w100*x101 + w100*x102 + w101*x100 + w101*x103 + w102*x101 + w103*x103 + w103,
w100*x101 + w100*x102 + w101*x100 + w101*x101 + w102*x100 + w102*x103 + w103*x102,
w100*x100 + w100*x103 + w101*x102 + w102*x101 + w103*x100,
w100*x100 + w100*x102 + w101*x100 + w101*x102 + w101*x103 + w102*x100 + w102*x101 + w103*x102 + w102,
w100*x100 + w100*x102 + w100*x103 + w101*x100 + w101*x101 + w102*x102 + w103*x100 + w100,
w100*x100 + w100*x101 + w101*x100 + w101*x103 + w102*x102 + w103*x101,
w100*x100 + w100*x101 + w100*x103 + w101*x101 + w102*x100 + w102*x102 + w103*x100 + x100,
w100*x100 + w100*x101 + w100*x102 + w101*x102 + w102*x100 + w102*x101 + w102*x103 + w103*x101 + x102]]
sage: C[0].groebner_basis()
Polynomial Sequence with 26 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)
The last output tells us that k001 and k003 can’t both be 1.
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.
Construct a new polynomial sequence object.
INPUT:
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
Bases: sage.structure.sequence.Sequence_generic
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:
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]
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]
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
Compute and return a Groebner basis for the ideal spanned by the polynomials in this system.
INPUT:
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
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^2)*k003 + 1,
k001 + (a^3)*k003 + (a + 1),
k000 + (a^3 + a^2 + a)*k003 + (a^3 + a^2 + a),
k103 + (a^3)*k003 + (a^2 + 1),
k102 + (a^3 + a^2 + a)*k003 + (a^3 + 1),
k101 + k003 + (a^2 + a),
k100 + (a^2)*k003 + (a^2 + a),
k003^2 + (a^3 + a^2 + a)*k003 + (a^3 + a^2 + a))
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
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
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
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
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
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)
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
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 : degrevlex
Names : k100, k101, k102, k103, x100, x101, x102, x103, w100, w101, w102, w103, s000, s001, s002, s003
Block 1 : Ordering : degrevlex
Names : k000, k001, k002, k003
Substitute variables for every polynomial in this system and return a new system. See MPolynomial.subs for calling convention.
INPUT:
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
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 : degrevlex
Names : k100, k101, k102, k103, x100, x101, x102, x103, w100, w101, w102, w103, s000, s001, s002, s003
Block 1 : Ordering : degrevlex
Names : k000, k001, k002, k003
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)
Bases: sage.rings.polynomial.multi_polynomial_sequence.PolynomialSequence_generic
Polynomial Sequences over .
Return a new system where linear leading variables are eliminated if the tail of the polynomial has length at most maxlength.
INPUT:
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
[c + d]
sage: R
[a + b + d]
Note
This is called “massaging” in [CBJ07].
Bases: sage.rings.polynomial.multi_polynomial_sequence.PolynomialSequence_generic
PolynomialSequence over , i.e extensions over
GF(2).
Project this polynomial system to .
That is, compute the Weil restriction of scalars for the
variety corresponding to this polynomial system and express it
as a polynomial system over .
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
Return True if F is a PolynomialSequence.
INPUT:
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