Complexity of arithmetic in a finite field? I am wondering what the complexities are of adding/subtracting and muliplying/dividing numbers in a finite field $\mathbb{F}_q$. I need it to understand an article I am reading.
Let $n = \lceil \log q \rceil$ (with "$\log$" being the base-2 logarithm, so $n$ is the size, in bits, of $q$).

If $q$ is a prime integer (i.e. $\mathbb{F}_q$ is the field of integers modulo $q$), then classical implementations will have cost $O(n)$ for addition and subtraction, $O(n^2)$ for multiplications and divisions. The cost of multiplications can be asymptotically lowered by using Toom-Cook multiplication or Fast Fourier Transform (with fast algorithms for the final modular reduction, whose name currently evades me), down to about $O(n(\log n)^2)$. However, for numbers of the size used in cryptography (say, 2048-bit integers), these methods tend not to be worth the effort, and plain Montgomery multiplication is faster. At least so goes the usual wisdom; each new hardware architecture may challenge such results. For modular divisions, the fastest algorithm is the extended binary GCD algorithm, which is quadratic.

One must note that even if Montgomery's multiplication and extended binary GCD are both in cost $O(n^2)$, the former tends to be, in practice, several dozen times faster than the latter, for numbers of the same size, because Montgomery's multiplication can rely on the hardware native multiplication opcode and process bits by chunks of 32 or 64, while binary GCD is a bit-by-bit algorithm.

If $q$ is a power of 2 ($q = 2^n$), then field $\mathbb{F}_q$ is the quotient field obtained by taking polynomials in $\mathbb{F}_2[X]$ modulo a given irreducible polynomial $P$. Since all finite fields of same cardinal are isomorphic, one can choose the polynomial $P$ to be almost empty, i.e. a trinomial ($P = 1 + X^a + X^n$) or a pentanomial ($P = 1 + X^a + X^b + X^c + X^n$). This allows for a linear reduction modulo $P$. In practice, multiplication will be done with Karatsuba's algorithm with complexity about $O(n^{1.585})$.

Also, in a binary field, squaring (and extracting a square root) can be done very efficiently, with $O(n)$ complexity. This is the Frobenius endomorphism, and is used to speed up computations on a special kind of elliptic curves called Koblitz curves. Squarings and square roots can be even further optimized to become "free" using normal bases, but this makes multiplication widely less efficient, so this is not considered to be a net gain in the general case.

Besides the Handbook of Applied Cryptography (especially chapters 2 and 14), a good reference is chapter 2 of the Guide to Elliptic Curve Cryptography, which covers finite field arithmetics -- and, lo! chapter 2 of that book is the "free sample" chapter that can be downloaded as a PDF from the Web site.