compute all degree d bivariate polynomials and evalute them

edit

What about:

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