fft-dihedral 0.1.0

Fast Fourier transforms for the dihedral group over prime finite fields

fft-dihedral

Fast Fourier transforms for the dihedral group over prime finite fields.

This package computes the Fourier transform of functions on

D_{2n} = <r, s | r^n = s^2 = e, srs^{-1} = r^{-1}>.

The fast path reduces the nonabelian dihedral transform to four cyclic number-theoretic transforms (NTTs).

Install

From PyPI, once published:

python -m pip install fft-dihedral

From a checkout:

python -m pip install -e ".[plot,dev]"

Quick Start

from fft_dihedral import (
    DEFAULT_MODULUS,
    dihedral_dft_fft,
    flatten_transform,
    root_of_unity,
)

n = 16
omega = root_of_unity(n, DEFAULT_MODULUS)
rotations = list(range(n))
reflections = [2 * k for k in range(n)]

transform = dihedral_dft_fft(rotations, reflections, DEFAULT_MODULUS, omega)
assert len(flatten_transform(transform)) == 2 * n

Conventions

A function f: D_{2n} -> GF(p) is represented by two length-n arrays:

rotations[k]   = f(r^k)
reflections[k] = f(s r^k)

For a primitive nth root of unity omega, the two-dimensional irreducible representations satisfy

rho_j(r^k)   = [[omega^(j k), 0], [0, omega^(-j k)]]
rho_j(s r^k) = [[0, omega^(-j k)], [omega^(j k), 0]]

With the normalized finite-group DFT convention

fhat(rho) = (1 / |D_{2n}|) sum_g f(g) rho(g),

each two-dimensional Fourier coefficient is assembled from four cyclic transforms:

fhat(rho_j) = 1/(2n) * [
  [DFT_omega(rotations)[j],    DFT_omega^{-1}(reflections)[j]],
  [DFT_omega(reflections)[j],  DFT_omega^{-1}(rotations)[j]]
]

The one-dimensional representations are computed by direct character sums.

Supported Fields

The implementation supports prime fields GF(p) when:

• n is a power of two for the fast transform.
• p is prime.
• n | p - 1, so GF(p) contains a primitive nth root of unity.
• gcd(2n, p) = 1, so the normalization by 1/(2n) is defined.

The default field is GF(2013265921), where

2013265921 = 15 * 2^27 + 1

so it supports power-of-two rotation orders up to 2^27.

True extension fields GF(p^k) are not implemented yet. This is intentionally stricter than integer quotient rings like Z/p^kZ; those are not fields when k > 1.

Arbitrary Compatible Primes

Roots are selected automatically using Sympy:

from fft_dihedral import root_of_unity

omega = root_of_unity(16, 97)

CLI verification over a non-default prime:

fft-dihedral verify --n 16 --modulus 97

You can also pass an explicit root:

fft-dihedral verify --n 16 --modulus 97 --omega 8

Verify

python -m pytest
fft-dihedral verify --n 128
fft-dihedral verify --n 16 --modulus 97

Benchmark

fft-dihedral bench --min-exp 4 --max-exp 15 --repetitions 5 --naive-limit 512
fft-dihedral bench --min-exp 4 --max-exp 6 --modulus 257 --repetitions 3

The benchmark prints FFT time / (2n log2(2n)). For an O(2n log(2n)) algorithm this ratio should stay roughly flat as n grows, modulo Python timing noise and cache effects.

Plot

Install the plotting extra:

python -m pip install "fft-dihedral[plot]"

Then generate PNG and SVG timing plots:

fft-dihedral-plot --min-exp 4 --max-exp 14 --repetitions 3 --naive-limit 1024

Limitations

• No inverse dihedral transform yet.
• No true extension-field GF(p^k) implementation yet.
• The radix-2 NTT is implemented in pure Python, so the Rust crate is much faster for production workloads.