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
R, gens) |
Construct an object representing the equations of a single round (e.g. of a block cipher).
Input:
sage: P.<x,y,z> = PolynomialRing(GF(2),3) sage: mq.MPolynomialRoundSystem(P,[x*y +1, z + 1]) [x*y + 1, z + 1]
arg1, [arg2=None]) |
Construct a new MPolynomialSystem.
Input:
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
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
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
self, R, gens) |
Construct an object representing the equations of a single round (e.g. of a block cipher).
Input:
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
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
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]
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
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
self) |
Substitute variables for every polynomial in self. See MPolynomial.subs for calling convention.
Input:
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]
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_
self, right) |
Addition is the union of generators.
Input:
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
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
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
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)]
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
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
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
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 ]
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]'
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
self, R, rounds) |
Construct a new system of multivariate polynomials. That is, a set of multivariate polynomials with at least one common root.
Input:
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
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:
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]
self, ij) |
Return an element of self.
Input:
sage: P.<a,b,c,d> = PolynomialRing(GF(127),4) sage: F = mq.MPolynomialSystem(sage.rings.ideal.Katsura(P))
-th polynomial overall
sage: F[0] # indirect doctest a + 2*b + 2*c + 2*d - 1
-th to
-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]
-th round,
-th polynomial
sage: F[0,1] a^2 + 2*b^2 + 2*c^2 + 2*d^2 - a
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'>)
self) |
Compute and return a Groebner basis for self.
Input:
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
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
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
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
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
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
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
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
self, i) |
Return
-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]
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
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:
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_
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
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
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
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
self, ij) |
See self.gen()
.
sage: P.<a,b,c,d> = PolynomialRing(GF(127),4) sage: F = mq.MPolynomialSystem(sage.rings.ideal.Katsura(P))
-th polynomial overall
sage: F[0] # indirect doctest a + 2*b + 2*c + 2*d - 1
-th to
-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]
-th round,
-th polynomial
sage: F[0,1] a^2 + 2*b^2 + 2*c^2 + 2*d^2 - a
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]
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
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
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_gf2e
Functions: change_ring
self, k) |
Project self onto
Input:
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.