Wed, 07. Nov 2007

$GF(2^n)$ arithmetic speed

Since version 2.8.10 Sage’s finite extension fields of characteristic 2 and degree $\ge 16$ are implemented via NTL’s GF2E rather than Pari. For some more or less random reason I timed how fast multiplying two random elements is now.

timings plot for GF(2^n)

The red line show the time it takes Magma 2.13-5 to multiply two random elements a million times for a given degree $n$. The green line shows the same calculation using Sage 2.8.12 with the default modulus and a Python loop. The blue line uses a Cython loop (== C loop) and the function good_modulus (see below) to generate a “good” modulus. The default modulus used by Sage is either the conway polynomial or - if we don’t know the conway polynomial - a random irreducible polynomial. I took the idea of using a “good” modulus from Michael Scott’s slides for his talk at the SPEED workshop. My attempt is not as sophisticated as his but naively searches for trinomials and pentanomials with low degree terms.

def good_modulus(n):
  P = GF(2)['x']
  x = P.gen()
  for a in xrange(1,n):
    f = x**n + x**a + 1
    if f.is_irreducible():
      return f
  for N in range(0,n,10):
    for a in xrange(1,N+1):
      for b in xrange(a+1,N+1):
        for c in xrange(b+1,N+1):
          f = x**n + x**c + x**b + x**a + 1
          if f.is_irreducible():
            return f
  # fall back to default if nothing was found
  return GF(2**n,'a').polynomial()

Some comments:

Up until $2^{15}$ we use Zech logarithms as they are implemented in Givaro. Magma uses Zech logarithms up to $2^{20}$ and we should do the same. If we use a Cython loop (i.e. remove the overhead of the loop) Sage’s arithmetic is as fast as Magma’s.
I don’t know why there is that peak around $n=2$ for Magma. Bug? My bad?
Magma scales quite nicely wordwise, as you would expect.
Surprisingly enough we beat Magma starting at $2^{100}$ up until at least $2^{128}$ using the “good” moduli.
What is going on with NTL between $2^{16}$ and $2^{64}$?

It seems we should internally - at least for large degrees - represent elements w.r.t. to a “good” modulus even if we know the conway polynomial.

posted at: 18:36 :: permanent link

Categories::

People::

Projects::

Bubble::

$GF(2^n)$ arithmetic speed