Are finite field computations slow?

edit

Not an answer, but it doesn't fit in a comment box and relevant, I think. With:

def test1():
    count = 0
    for a in k:
        for b in k:
            if not f.subs(x=a, y=b):
                count += 1
    return count

def test2():
    count = 0
    for a in k:
        for b in k:
            if not f(a, b):
                count += 1
    return count

def test3():
    count = 0
    for a in k:
        for b in k:
            if not (b^3+b+4*a):
                count += 1
    return count

we get

sage: timeit('test1()')
25 loops, best of 3: 24.6 ms per loop
sage: timeit('test2()')
5 loops, best of 3: 64.1 ms per loop
sage: timeit('test3()')
125 loops, best of 3: 2.73 ms per loop

so, surprisingly, subs is quite a bit faster than "polynomial evaluation", and unsurprisingly writing out the expression explicitly is of course even faster than either.

The subs method gives back a result in a ring that's a little too large for the purposes, though (this is as documented):

sage: parent(f.subs(x=k(1),y=k(1))) 
Multivariate Polynomial Ring in x, y over Finite Field in a of size 5^2
sage: parent(f(k(1),k(1))) 
Finite Field in a of size 5^2

You are not using it the correct way. You defined f(x,y) over the symbolic ring but then you are doing the computations f(a, b) over the finite field. So, at every step it has to coerce everything to the finite field. You should be using the PolynomialRing to get your variables and constants coerced to the finite field at the very outset.

Try the following code. It is fast.

f(x,y) = y^3 + y + 4*x
print "Original polynomial's base ring:", f.base_ring()
k = GF(25, 'a')
F.<x,y> = PolynomialRing(k)  # x,y are not symbolic variables now
f = y^3 + y + 4*x
print "New base ring:", f.base_ring()
count = 0
for a in k:
    for b in k:
        if not f.subs(x=a, y=b):
            count += 1
print count

The output of above:

Original polynomial's base ring: Symbolic Ring
New base ring: Finite Field in a of size 5^2
25