17.9 Multivariate Polynomial Systems

Module: sage.crypto.mq.mpolynomialsystem

Multivariate Polynomial Systems.

We call a finite set of multivariate polynomials an MPolynomialSystem.

Furthermore we assume that these multivariate polynomials have a common solution if interpreted as equations where the left hand side is the polynomial and the right hand side is equal to zero. Or in other terms: The set of multivariate polynomials have common roots. In many other computer algebra systems this class could be called Ideal but - strictly speaking - an ideal is a very distinct object form its generators and thus this is not an Ideal in Sage.

The main purpose of this class is to manipulate an MPolynomialSystem to gather the common solution.

This idea is specialized to an MPolynomialSystem which consists of several rounds. These kind of polynomial systems are often found in symmetric algebraic cryptanalysis. The most prominent examples of these kind of systems are: SR (AES), Flurry/Curry, and CTC(2).

Author: Martin Albrecht (malb@informatik.uni-bremen.de)

TEST:

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

Module-level Functions

MPolynomialRoundSystem( R, gens)

Construct an object representing the equations of a single round (e.g. of a block cipher).

Input:

R
- base ring
gens
- list (default: [])

sage: P.<x,y,z> = PolynomialRing(GF(2),3)
sage: mq.MPolynomialRoundSystem(P,[x*y +1, z + 1])
[x*y + 1, z + 1]

MPolynomialSystem( arg1, [arg2=None])

Construct a new MPolynomialSystem.

Input:

arg1
- a multivariate polynomial ring or an ideal
arg2
- an iterable object of rounds, preferable MPolynomialRoundSystem, or polynomials (default:None)

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

If a list of MPolynomialRoundSystems is provided those form the rounds.

sage: mq.MPolynomialSystem(I.ring(), [mq.MPolynomialRoundSystem(I.ring(),I.gens())])
Polynomial System with 4 Polynomials in 4 Variables

If an ideal is provided the generators are used.

sage: mq.MPolynomialSystem(I)
Polynomial System with 4 Polynomials in 4 Variables

If a list of polynomials is provided the system has only one round.

sage: mq.MPolynomialSystem(I.ring(), I.gens())
Polynomial System with 4 Polynomials in 4 Variables

is_MPolynomialRoundSystem( F)

Return True if F is an MPolynomialRoundSystem

sage: P.<x,y> = PolynomialRing(QQ)
sage: I = [[x^2 + y^2], [x^2 - y^2]]
sage: F = mq.MPolynomialSystem(P,I); F
Polynomial System with 2 Polynomials in 2 Variables
sage: mq.is_MPolynomialRoundSystem(F.round(0))
True

is_MPolynomialSystem( F)

Return True if F is an MPolynomialSystem

sage: P.<x,y> = PolynomialRing(QQ)
sage: I = [[x^2 + y^2], [x^2 - y^2]]
sage: F = mq.MPolynomialSystem(P,I); F
Polynomial System with 2 Polynomials in 2 Variables
sage: mq.is_MPolynomialSystem(F)
True

Class: MPolynomialRoundSystem_generic

class MPolynomialRoundSystem_generic
MPolynomialRoundSystem_generic( self, R, gens)

Construct an object representing the equations of a single round (e.g. of a block cipher).

Input:

R
- base ring
gens
- list (default: [])

sage: P.<x,y,z> = PolynomialRing(GF(2),3)
sage: mq.MPolynomialRoundSystem(P,[x*y +1, z + 1])
[x*y + 1, z + 1]

Functions: gens,$ \,$ monomials,$ \,$ ngens,$ \,$ ring,$ \,$ subs,$ \,$ variables

gens( self)

Return list of polynomials in self.

sage: sr = mq.SR(allow_zero_inversions=True,gf2=True,order='block')
sage: F,s = sr.polynomial_system()
sage: R1 = F.round(1)
sage: l = R1.gens()
sage: l[0]
k000^2 + k000

monomials( self)

Return unordered list of monomials appearing in polynomials in self.

sage: sr = mq.SR(allow_zero_inversions=True,gf2=True,order='block')
sage: F,s = sr.polynomial_system()
sage: R1 = F.round(1)
sage: sorted(R1.monomials())
[k003, k002, k001, k000, k003^2, k002^2, k001^2, k000^2]

ngens( self)

Return number of polynomials in self.

sage: sr = mq.SR(allow_zero_inversions=True,gf2=True,order='block')
sage: F,s = sr.polynomial_system()
sage: R0 = F.round(0)
sage: R0.ngens()
4

ring( self)

Return the base ring.

sage: sr = mq.SR(allow_zero_inversions=True,gf2=True,order='block')
sage: F,s = sr.polynomial_system()
sage: R0 = F.round(0)
sage: print R0.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

subs( self)

Substitute variables for every polynomial in self. See MPolynomial.subs for calling convention.

Input:

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

sage: sr = mq.SR(allow_zero_inversions=True,gf2=True,order='block')
sage: F,s = sr.polynomial_system()
sage: R1 = F.round(1)
sage: R1.subs(s) # the solution
sage: R1
[0, 0, 0, 0]

variables( self)

Return unordered list of variables apprearing in polynomials in self.

sage: sr = mq.SR(allow_zero_inversions=True,gf2=True,order='block')
sage: F,s = sr.polynomial_system()
sage: R1 = F.round(1)
sage: sorted(R1.variables())
[k003, k002, k001, k000]

Special Functions: __add__,$ \,$ __cmp__,$ \,$ __contains__,$ \,$ __copy__,$ \,$ __getitem__,$ \,$ __init__,$ \,$ __iter__,$ \,$ __len__,$ \,$ _magma_,$ \,$ _repr_,$ \,$ _singular_

__add__( self, right)

Addition is the union of generators.

Input:

right
- MPolynomialSystem, list or tuple

sage: sr = mq.SR(allow_zero_inversions=True,gf2=True,order='block')
sage: F,s = sr.polynomial_system()
sage: R1 = F.round(1)
sage: len(R1 + F.round(2)) # indirect doctest
28
sage: len(R1 + list(F.round(2)))
28

__cmp__( self, other)

Compare the ring and generators of self and other.

sage: sr = mq.SR(allow_zero_inversions=True)
sage: F,s = sr.polynomial_system()
sage: F == copy(F) # indirect doctest
True

__contains__( self, element)

Return True if element is in the list of generators for self.

sage: sr = mq.SR(allow_zero_inversions=True,gf2=True,order='block')
sage: F,s = sr.polynomial_system()
sage: R1 = F.round(1)
sage: P = F.ring()
sage: f = P('k000^2 + k000')
sage: f in R1
True
sage: f+1 in R1
False

__copy__( self)

Return a copy of this round system.

       sage: sr = mq.SR(allow_zero_inversions=True)
       sage: F,s = sr.polynomial_system()
sage: r = F.round(0)
       sage: copy(r)
[w100 + k000 + (a^3 + a + 1), w101 + k001 + (a^3 + 1),
w102 + k002 + (a^3 + a^2 + 1), w103 + k003 + (a^3 + a^2 +
a)]

__getitem__( self, i)

Return the i-th generator of self.

sage: P.<x,y,z> = PolynomialRing(GF(2),3)
sage: F = mq.MPolynomialRoundSystem(P,[x*y +1, z + 1])
sage: F[0] # indirect doctest
x*y + 1

__iter__( self)

Iterate over the generators of self.

sage: P.<x,y,z> = PolynomialRing(GF(2),3)
sage: F = mq.MPolynomialRoundSystem(P,[x*y +1, z + 1])
sage: for f in F:
...     print f
x*y + 1
z + 1

__len__( self)

Return self.ngens().

sage: P.<x,y,z> = PolynomialRing(GF(2),3)
sage: F = mq.MPolynomialRoundSystem(P,[x*y +1, z + 1])
sage: len(F)
2

_magma_( self)

Return MAGMA ideal representation of self.

sage: sr = mq.SR(allow_zero_inversions=True,gf2=True)
sage: F,s = sr.polynomial_system()
sage: R1 = F.round(1)
sage: R1._magma_() # optional, requires MAGMA
Ideal of Polynomial ring of rank 20 over GF(2)
Graded Reverse Lexicographical Order
Variables: k100, k101, k102, k103, x100, x101, x102, x103, w100, w101,
w102, w103, s000, s001, s002, s003, k000, k001, k002, k003
Basis:
[
k000^2 + k000,
k001^2 + k001,
k002^2 + k002,
k003^2 + k003
]

_repr_( self)

Return string representation of self.

sage: P.<x,y,z> = PolynomialRing(GF(2),3)
sage: F = mq.MPolynomialRoundSystem(P,[x*y +1, z + 1])
sage: str(F) # indirect doctest
'[x*y + 1, z + 1]'

_singular_( self)

Return SINGULAR ideal representation of self.

sage: sr = mq.SR(allow_zero_inversions=True,gf2=True,order='block')
sage: F,s = sr.polynomial_system()
sage: R1 = F.round(1)
sage: R1._singular_()
k000^2+k000,
k001^2+k001,
k002^2+k002,
k003^2+k003

Class: MPolynomialSystem_generic

class MPolynomialSystem_generic
MPolynomialSystem_generic( self, R, rounds)

Construct a new system of multivariate polynomials. That is, a set of multivariate polynomials with at least one common root.

Input:

arg1
- a multivariate polynomial ring or an ideal
arg2
- an iterable object of rounds, preferable MPolynomialRoundSystem, or polynomials (default:None)

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

If a list of MPolynomialRoundSystems is provided those form the rounds.

sage: mq.MPolynomialSystem(I.ring(), [mq.MPolynomialRoundSystem(I.ring(),I.gens())])
Polynomial System with 4 Polynomials in 4 Variables

If an ideal is provided the generators are used.

sage: mq.MPolynomialSystem(I)
Polynomial System with 4 Polynomials in 4 Variables

If a list of polynomials is provided the system has only one round.

sage: mq.MPolynomialSystem(I.ring(), I.gens())
Polynomial System with 4 Polynomials in 4 Variables

Functions: coefficient_matrix,$ \,$ gen,$ \,$ gens,$ \,$ groebner_basis,$ \,$ ideal,$ \,$ monomials,$ \,$ ngens,$ \,$ nmonomials,$ \,$ nrounds,$ \,$ nvariables,$ \,$ ring,$ \,$ round,$ \,$ rounds,$ \,$ subs,$ \,$ variables

coefficient_matrix( self, [sparse=True])

Return tuple (A,v) where A is the coefficent matrix of self and v the matching monomial vector. Monomials are order w.r.t. the term ordering of self.ring() in reverse order.

Input:

sparse
- construct a sparse matrix (default: True)

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 = mq.MPolynomialSystem(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]

gen( self, ij)

Return an element of self.

Input:

ij
- tuple, slice, integer

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

$ ij$ -th polynomial overall

sage: F[0] # indirect doctest
a + 2*b + 2*c + 2*d - 1

$ i$ -th to $ j$ -th polynomial overall

sage: F[0:2]
[a + 2*b + 2*c + 2*d - 1, a^2 + 2*b^2 + 2*c^2 + 2*d^2 - a]

$ i$ -th round, $ j$ -th polynomial

sage: F[0,1]
a^2 + 2*b^2 + 2*c^2 + 2*d^2 - a

gens( self)

Return list of polynomials in self

sage: sr = mq.SR(allow_zero_inversions=True)
sage: F,s = sr.polynomial_system()
sage: l = F.gens()
sage: len(l), type(l)
(40, <type 'tuple'>)

groebner_basis( self)

Compute and return a Groebner basis for self.

Input:

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

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( self)

Return SAGE ideal spanned by self.gens()

These computations use pseudo-random numbers, so we set the seed for reproducible testing.

sage: set_random_seed(0)

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, (a^3)*k001 + (a^3 + a^2)*k003 + 
(a^3 + a + 1), k000 + (a^3 + a^2 + a)*k003 + (a^3 + a^2 + a), 
(a^2)*k103 + (a^2 + a)*k003 + (a^2 + a + 1), (a^3)*k102 + 
(a^3 + 1)*k003 + (a^2), (a^3)*k101 + (a^3)*k003 + (a^2 + 1), 
(a^3)*k100 + (a^2 + a)*k003 + (a^2 + 1), 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

monomials( self)

Return a list of monomials in self.

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

ngens( self)

Return number polynomials in self

sage: sr = mq.SR(allow_zero_inversions=True,gf2=True,order='block')
sage: F,s = sr.polynomial_system()
sage: F.ngens()
56

nmonomials( self)

Return the number of monomials present in self.

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

nrounds( self)

Return number of rounds of self.

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

nvariables( self)

Return number of variables present in self.

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

ring( self)

Return base ring.

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

round( self, i)

Return $ i$ -th round of self.

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

rounds( self)

Return list of rounds of self.

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

subs( self)

Substitute variables for every polynomial in self. See MPolynomial.subs for calling convention.

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

Input:

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

variables( self)

Return all variables present in self. This list may or may not be equal to the generators of the ring of self.

sage: sr = mq.SR(allow_zero_inversions=True)
sage: F,s = sr.polynomial_system()
sage: F.variables()[:10]  # this output ordering depends on a hash and so might change if __hash__ changes
[s000, k101, k100, s003, x102, x103, s002, w103, w102, x100]        #
32-bit
[k101, k100, s003, x102, x103, s002, w103, w102, x100, x101]        #
64-bit

Special Functions: __add__,$ \,$ __cmp__,$ \,$ __contains__,$ \,$ __copy__,$ \,$ __getitem__,$ \,$ __init__,$ \,$ __iter__,$ \,$ _magma_,$ \,$ _repr_,$ \,$ _singular_

__add__( self, right)

Add polynomial systems together, i.e. create a union of their polynomials.

sage: P.<a,b,c,d> = PolynomialRing(GF(127))
sage: I = sage.rings.ideal.Katsura(P)
sage: F = mq.MPolynomialSystem(I)
sage: F + [a^127 + a]
       Polynomial System with 5 Polynomials in 4 Variables

sage: F + P.ideal([a^127 + a])
       Polynomial System with 5 Polynomials in 4 Variables

sage: F + mq.MPolynomialSystem(P,[a^127 + a])
Polynomial System with 5 Polynomials in 4 Variables

__cmp__( self, other)

Compare the ring and rounds of self and other.

sage: sr = mq.SR(allow_zero_inversions=True)
sage: F,s = sr.polynomial_system()
sage: F == copy(F) # indirect doctest
True

__contains__( self, element)

Return True if element is in self or False else. This method does not return an answer for the ideal spanned by the generators of this system but literately whether a polynomial is in the list of generators.

       sage: P.<x0,x1,x2,x3> = PolynomialRing(GF(37))
       sage: I = sage.rings.ideal.Katsura(P)
       sage: F = mq.MPolynomialSystem(I)
sage: f = x0 + 2*x1 + 2*x2 + 2*x3 -1 
sage: f in F
True
sage: x0*f in F
False
sage: x0*f in F.ideal()
True

__copy__( self)

Return a copy of self. While this is not a deep copy only mutable members of this system are copied.

       sage: sr = mq.SR(allow_zero_inversions=True)
       sage: F,s = sr.polynomial_system()
       sage: copy(F) # indirect doctest
Polynomial System with 40 Polynomials in 20 Variables

__getitem__( self, ij)

See self.gen().

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

$ ij$ -th polynomial overall

sage: F[0] # indirect doctest
a + 2*b + 2*c + 2*d - 1

$ i$ -th to $ j$ -th polynomial overall

sage: F[0:2]
[a + 2*b + 2*c + 2*d - 1, a^2 + 2*b^2 + 2*c^2 + 2*d^2 - a]

$ i$ -th round, $ j$ -th polynomial

sage: F[0,1]
a^2 + 2*b^2 + 2*c^2 + 2*d^2 - a

__iter__( self)

Return an iterator for self where all polynomials in self are yielded in order as they appear in self.

sage: P.<x0,x1,x2,x3> = PolynomialRing(GF(37))
sage: I = sage.rings.ideal.Katsura(P)
sage: F = mq.MPolynomialSystem(P,I.gens())
sage: list(F)
[x0 + 2*x1 + 2*x2 + 2*x3 - 1,
x0^2 + 2*x1^2 + 2*x2^2 + 2*x3^2 - x0,
2*x0*x1 + 2*x1*x2 + 2*x2*x3 - x1,
x1^2 + 2*x0*x2 + 2*x1*x3 - x2]

_magma_( self)

Return MAGMA ideal representation of this system as an ideal.

sage: sr = mq.SR(allow_zero_inversions=True,gf2=True)
sage: F,s = sr.polynomial_system()
sage: F._magma_() # optional, requires MAGMA

_repr_( self)

Return a string representation of this system.

sage: P.<a,b,c,d> = PolynomialRing(GF(127))
sage: I = sage.rings.ideal.Katsura(P)
sage: F = mq.MPolynomialSystem(I); F # indirect doctest
Polynomial System with 4 Polynomials in 4 Variables

_singular_( self)

Return SINGULAR ideal representation of this system.

sage: P.<a,b,c,d> = PolynomialRing(GF(127))
sage: I = sage.rings.ideal.Katsura(P)
sage: F = mq.MPolynomialSystem(I); F
Polynomial System with 4 Polynomials in 4 Variables
sage: F._singular_()
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

Class: MPolynomialSystem_gf2

class MPolynomialSystem_gf2
MPolynomialSystem over GF(2).

Class: MPolynomialSystem_gf2e

class MPolynomialSystem_gf2e
MPolynomialSystem over $ GF(2^e)$ .

Functions: change_ring

change_ring( self, k)

Project self onto $ k$

Input:

k
- GF(2) (parameter only for compatible syntax)

sage: k.<a> = GF(2^2)
sage: P.<x,y> = PolynomialRing(k,2)
sage: a = P.base_ring().gen()
sage: F = mq.MPolynomialSystem(P,[x*y + 1, a*x + 1])
sage: F
Polynomial System with 2 Polynomials in 2 Variables
sage: F2 = F.change_ring(GF(2)); F2
Polynomial System with 8 Polynomials in 4 Variables
sage: F2.gens()
(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)

NOTE: Based on SINGULAR implementation by Michael Brickenstein <brickenstein@googlemail.com>

See About this document... for information on suggesting changes.