Complexity of arithmetic in a finite field?

Question

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.

Answer 1

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.

Answer 2

Well, if $q$ is a prime (and not $p^n$ with $n>1$), then addition, subtraction and multiplication can be performed by doing the traditional operations modulo $q$, that is:

$a +_{\mathbb{F}_q}b \equiv (a+b) \bmod q$

$a -_{\mathbb{F}_q}b \equiv (a-b) \bmod q$

$a \times_{\mathbb{F}_q}b \equiv (a\times b) \bmod q$

As such, addition and subtraction can be done in time $O(log(q))$, while multiplication is typically done in time $O(log^2(q))$. Now, there are multiplication/modulo methods that are asymptotically faster, but they are typically slower for the range of $q$'s that we usually see in practice in cryptography; however, if your $q$ is huge, it would be reasonable to use these faster methods.

The tricky one is division; that is not division on the field of integers followed by a modulus operation. Instead, it involves finding the multiplicative inverse of a number; that is, given $b$, we find the field member $b^{-1}$ such that $b \times b^{-1} = 1$. Then, $a / b = a \times b^{-1}$

Multiplicative inverses are typically found using the Extended Euclidean Method; a straight-forward implementation takes $O(log^3(q))$ time. Again, there are optimizations that you can do; however, division still is the most costly of the four operations (to the extent that we typically arrange the calculations to minimize the number of divisions, even at a cost of increasing the number of multiplies).

Answer 3

The Handbook on Applied Cryptography (link to the pdf version is on Alfred's webpage) has some of the known techniques to do finite field arithematic. If you are doing arithmetic to implement Elliptic Curve Cryptography (note the comment made by Paulo), then there are methods that depends on whether you are doing it in Jacobian or Projective plane (inverse works fine in Jacobian and addition works great on Projective planes). You can refer to this paper for more ground level details. There has been considerable improvements to all the algorithms stated in the paper, but they involve more complex methods.