# compute all degree d bivariate polynomials and evalute them

I want to compute all degree <=d polynomials, of form f1(x1)g1(x2)+f2(x1)g2(x2), from GF(2)[x1, x2] and then evaluate them at a certain polynomial input

eg degree d <= 1 and evaluation at (p^2, p^3 +1)

0 -> 0

1 -> 1

x1 -> p^2

x1 + 1 -> p^2 + 1

x2 -> p^3 + 1

x2 + 1 -> p^3

x1 + x2 -> p^2 + p^3 + 1

x1 + x2 + 1 -> p^2 + p^3

edit retag close merge delete

Sort by ยป oldest newest most voted

R.<x1,x2>=GF(2)[]
d=1
li=[x1^a*x2^b for a in range(d+1) for b in range(d+1) if a+b<=d]
sub=Subsets(li)
pol_d=[sum(el) for el in sub]
pol_d

[0, 1, x2, x1, x2 + 1, x1 + 1, x1 + x2, x1 + x2 + 1]

P.<p>=GF(2)[]
[pol_d[0],pol_d[1]]+[pol_d[i](x1=p^2,x2=p^3+1)
for i in range(2,len(pol_d))]

[0, 1, p^3 + 1, p^2, p^3, p^2 + 1, p^3 + p^2 + 1, p^3 + p^2]


(Edit)

This worked for me for d=5

R.<x1,x2>=GF(2)[]
P.<p>=GF(2)[]
d=5
K1.<x1>=GF(2)[]
K2.<x2>=GF(2)[]
K1of = lambda deg: list(K1.polynomials(of_degree=deg))
K2of = lambda deg: list(K2.polynomials(of_degree=deg))
for i in range(d+1):
for a in K1of(i):
for b in K2of(d-i):
for j in range(d+1):
for c in K1of(j):
for e in K2of(d-j):
w=R(a)*R(b)+R(c)*R(e)
q=w(x1=p^2,x2=p^3+1)
if q.is_zero() and not (a-c).is_zero():
print(' a =',a,'\n','b =',b,'\n',
'c =',c,'\n','e =',e,'\n','q =',q,'\n')

a = x1^3
b = x2^2
c = x1^3 + 1
e = x2^2 + 1
q = 0

a = x1^3 + 1
b = x2^2 + 1
c = x1^3
e = x2^2
q = 0

more

Hi, Thank you. I was able to adapt your first code to the problem I stated in the description. But, for d=5, the computation has blew up and I wanted to check till d= 6 or 7. Can you suggest how to make it more efficient. Since, I am new to sage, I am not sure whether something more efficient in-built things exist or not. Basically, I want to check that some polynomial of form h = f1(x1)g1(x2) + f2(x1)g2(x2), over GF(2), evaluates to zero or not after I plug in the mapping (p_2, p^3 + 1).

My solution was to nest 4 way loop to build h and then plug in mapping each time.

( 2023-01-16 16:08:37 +0200 )edit

Maybe you should demonstrate your solution. If the addends of h are identical, then h=0, so maybe some additional assumptions are needed.

( 2023-01-17 01:51:36 +0200 )edit