Ask Your Question
0

Problem deleting duplicate values in a list of polynomials

asked 2021-08-10 14:39:41 +0200

updated 2022-04-14 20:37:45 +0200

FrédéricC gravatar image

I am working with variables over GF(2) and when I list the summands of certain polynomials, I want to have a list of all distinct polynomials, but it does not work.

from sage.crypto.sbox import SBox
from sage.crypto.boolean_function import BooleanFunction
F=GF(2^4,'a');
V=F.vector_space();
V=sorted(V);
sF=sorted(F);

S= SBox(12,5,6,11,9,0,10,13,3,14,15,8,4,7,1,2); #Present SBox
f=S.interpolation_polynomial(); #univariate form

L=[S.component_function(i).algebraic_normal_form() for i in [1,2,4,8]];
L # S=(f1,f2,f3,f4)
#L=[x0 + x1*x2 + x2 + x3,
x0*x1*x2 + x0*x1*x3 + x0*x2*x3 + x1*x3 + x1 + x2*x3 + x3,
x0*x1*x3 + x0*x1 + x0*x2*x3 + x0*x3 + x1*x3 + x2 + x3 + 1,
x0*x1*x2 + x0*x1*x3 + x0*x2*x3 + x0 + x1*x2 + x1 + x3 + 1]


S=set(srange(4)); #[0,1,2,3]
C2=Combinations(S,2).list();
C1=Combinations(S,1).list();
A=list(var('a%d' % i,domain='integer') for i in srange(len(C2)+len(C1)));
R.<x0,x1,x2,x3>=GF(2)[];
X=[x0,x1,x2,x3];
def g(X):
    return [X[i[0]]*X[i[1]] for i in C2]+[X[i[0]] for i in C1];
L_S=[g(L)[i] for i in [0..len(A)-1]];
L_X=[g(X)[i] for i in [0..len(A)-1]];

M0=[(L_S[i]+L_X[i]) for i in [0..len(A)-1]]

Now, this is what M0 looks like:

[x0*x1*x2 + x0*x1*x3 + x0*x3 + x2*x3 + x3,
 x0*x1 + x0*x3 + x0 + x1*x2*x3 + x1*x3,
 x0*x1*x2 + x0*x1 + x0*x2*x3 + x0*x2 + x0*x3 + x1*x2 + x1*x3 + x2*x3 + x2,
 x0*x1*x2 + x0*x1*x3 + x0*x1 + x0*x3 + x1,
 x0*x1*x3 + x0*x1 + x0*x2*x3 + x0*x3 + x1*x2,
 x0*x1*x3 + x0*x1 + x0*x2 + x0 + x1*x2 + x1 + x2 + x3 + 1,
 x1*x2 + x2 + x3,
 x0*x1*x2 + x0*x1*x3 + x0*x2*x3 + x1*x3 + x2*x3 + x3,
 x0*x1*x3 + x0*x1 + x0*x2*x3 + x0*x3 + x1*x3 + x3 + 1,
 x0*x1*x2 + x0*x1*x3 + x0*x2*x3 + x0 + x1*x2 + x1 + 1]

When I flatten and use set() I get that set(flatten(M0)) equals:

{1,
 1,
 x0,
 x0,
 x0,
 x0*x1,
 x0*x1,
 x0*x1,
 x0*x1*x2,
 x0*x1*x2,
 x0*x1*x2,
 x0*x1*x3,
 x0*x1*x3,
 x0*x1*x3,
 x0*x1*x3,
 x0*x2,
 x0*x2,
 x0*x2*x3,
 x0*x2*x3,
 x0*x2*x3,
 x0*x2*x3,
 x0*x3,
 x0*x3,
 x0*x3,
 x1,
 x1,
 x1,
 x1*x2,
 x1*x2,
 x1*x2,
 x1*x2,
 x1*x2*x3,
 x1*x3,
 x1*x3,
 x1*x3,
 x2,
 x2,
 x2*x3,
 x2*x3,
 x3,
 x3,
 x3}

Why are there duplicate values if I have set() operation?

edit retag flag offensive close merge delete

1 Answer

Sort by » oldest newest most voted
0

answered 2021-08-17 16:53:53 +0200

Max Alekseyev gravatar image

updated 2021-08-17 17:07:46 +0200

First, I cannot reproduce your result of set(flatten(M0)) in Sage 9.3 - it just gives a set of polynomials from M0.

Second, elements of M0 have type class 'sage.rings.polynomial.pbori.pbori.BooleanPolynomial' and are composed on monomials of type class 'sage.rings.polynomial.pbori.pbori.BooleanMonomial'. Apparently Sage has trouble to comparing them with each other (which may be worth to report as a bug).

Third, to avoid dealing with Boolean polynomials/monomials, we can convert them to polynomials over GF(2) (defined by the ring R in your code) when defining M0 as

M0 = [ R(L_S[i]+L_X[i]) for i in [0..len(A)-1] ]

Then, the result you want can be achieved as

set(flatten(list(map(lambda t: t.monomials(),M0))))

or without explicit conversion of map to list as

import functools
functools.reduce(set.union,map(lambda t: t.monomials(),M0),set())

Each of these gives the combined set of monomials {1, x0, x0*x1, x2, x1*x2, x0*x1*x2, x3, x1*x2*x3, x0*x3, x1*x3, x1, x0*x1*x3, x0*x2, x0*x2*x3, x2*x3}.

edit flag offensive delete link more

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

1 follower

Stats

Asked: 2021-08-10 14:39:41 +0200

Seen: 69 times

Last updated: Aug 17 '21