# How to transform a univariate polynomial over $\mathbb{F}_{2^n}$ into a multivariate Boolean polynomial over $\mathbb{F}_2^n$

.

F=GF(2^8,'a')
R=PolynomialRing(F,"x,y")
R.inject_variables()
f=x*y-1


How can we transform f into a multivariable Boolean polynomial over $\mathbb{F}_{2^8}$, which includes variables $x_0, \ldots, x_7$ and $y_0, \ldots, y_7$ (16 variables in total), and has an algebraic degree of 2?

edit retag close merge delete

Edited for legibility.

( 2024-07-26 09:29:44 +0200 )edit

You do not specify your "transformation". We may assume something like :

(a^7 + a^5 + a^3 + a^2 + 1)*x^2*y --> (x7+x5+x3+x2+1)^2*(y7+y5+y3+y2+1)


but (as usual) "assume" = "make an ass of you and me"...

Can you specify what you want ?

In the interim, look up hom?...

( 2024-07-26 10:54:20 +0200 )edit

Sort by ยป oldest newest most voted

ASSUMING a transformation along the lines of :

(a^7 + a^5 + a^3 + a^2 + 1)*x^2*y --> (x7+x5+x3+x2+1)^2*(y7+y5+y3+y2+1)


we may define the target ring as

R1=PolynomialRing(GF(2), ["x%d"%u for u in range(8)] +\
["y%d"%u for u in range(8)])
R1.inject_variables()


We remark that the coefficients of any monomial of an element of R is either 0 or 1, and thus can be ignored.

We need to translate each element of F into a polynomial of R in x and in y according to the assumed meaning :

from sage.symbolic.operators import mul_vararg as mv
Dx={t:sum(map(mv, R1.gens()[:8],list(t))) for t in F}
Dy={t:sum(map(mv, R1.gens()[8:],list(t))) for t in F}
Dall=dict(zip(R.gens(), (Dx, Dy)))


The transcription function is then trivial using the properties of polynomials representation in Sage :

def trans(p):
return sum([product([Dall[v][u[0]]^(u[1].degree(v))
for v in R.gens()])
for u in list(p)])


A couple checks :

sage: trans(f)
x0 + y0 + 1
sage: foo=R.random_element(degree=2) ; foo
(a^7 + a^4 + a + 1)*x^2 + (a^7 + a^6 + a^4 + a^3 + a^2 + 1)*x*y + (a^6 + a^5 + a^4 + a^3 + a)*y^2 + (a^7 + a^6 + a + 1)*x + (a^6 + a^5 + a^3 + a + 1)
sage: trans(foo)
x0^2 + x1^2 + x4^2 + x7^2 + x0*y0 + x2*y0 + x3*y0 + x4*y0 + x6*y0 + x7*y0 + y1^2 + x0*y2 + x2*y2 + x3*y2 + x4*y2 + x6*y2 + x7*y2 + x0*y3 + x2*y3 + x3*y3 + x4*y3 + x6*y3 + x7*y3 + y3^2 + x0*y4 + x2*y4 + x3*y4 + x4*y4 + x6*y4 + x7*y4 + y4^2 + y5^2 + x0*y6 + x2*y6 + x3*y6 + x4*y6 + x6*y6 + x7*y6 + y6^2 + x0*y7 + x2*y7 + x3*y7 + x4*y7 + x6*y7 + x7*y7 + x0 + x1 + x6 + x7 + 1


HTH,

more