Metadata-Version: 2.4
Name: fft-dihedral
Version: 0.1.1
Summary: Fast Fourier transforms for the dihedral group over prime finite fields
Author: Walters Labs
License-Expression: MIT
Project-URL: Homepage, https://github.com/walters-labs/fft-dihedral-py
Project-URL: Repository, https://github.com/walters-labs/fft-dihedral-py
Project-URL: Issues, https://github.com/walters-labs/fft-dihedral-py/issues
Keywords: fft,ntt,dihedral,finite-groups,fourier
Classifier: Development Status :: 3 - Alpha
Classifier: Intended Audience :: Science/Research
Classifier: Programming Language :: Python :: 3
Classifier: Programming Language :: Python :: 3.10
Classifier: Programming Language :: Python :: 3.11
Classifier: Programming Language :: Python :: 3.12
Classifier: Programming Language :: Python :: 3.13
Classifier: Programming Language :: Python :: 3.14
Classifier: Topic :: Scientific/Engineering :: Mathematics
Requires-Python: >=3.10
Description-Content-Type: text/markdown
License-File: LICENSE
Requires-Dist: sympy>=1.12
Provides-Extra: plot
Requires-Dist: matplotlib>=3.8; extra == "plot"
Requires-Dist: numpy>=1.23; extra == "plot"
Provides-Extra: dev
Requires-Dist: build>=1.0; extra == "dev"
Requires-Dist: pytest>=8.0; extra == "dev"
Requires-Dist: ruff>=0.7; extra == "dev"
Requires-Dist: twine>=5.0; extra == "dev"
Dynamic: license-file

# fft-dihedral

[![PyPI](https://img.shields.io/pypi/v/fft-dihedral.svg)](https://pypi.org/project/fft-dihedral/)
[![License: MIT](https://img.shields.io/badge/License-MIT-yellow.svg)](LICENSE)
[![Python](https://img.shields.io/badge/python-3.10%2B-blue.svg)](https://www.python.org/)

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

This package computes the Fourier transform of functions on

```text
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). The inverse transform reconstructs two
cyclic spectra and applies two inverse NTTs.

## Install

From PyPI:

```bash
python -m pip install fft-dihedral
```

From a checkout:

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

## Quick Start

```python
from fft_dihedral import (
    DEFAULT_MODULUS,
    dihedral_dft_fft,
    dihedral_inverse_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
assert dihedral_inverse_fft(transform, omega) == (rotations, reflections)
```

## Conventions

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

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

For a primitive `n`th root of unity `omega`, the two-dimensional irreducible
representations satisfy

```text
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

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

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

```text
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.

## What The Four NTTs Do

The input vector is really two vectors:

```text
rotations   = [f(1), f(r), ..., f(r^{n-1})]
reflections = [f(s), f(sr), ..., f(sr^{n-1})]
```

The FFT applies cyclic NTTs to those two vectors with both orientations of the
root:

```text
A^+ = NTT_omega(rotations)
A^- = NTT_omega^{-1}(rotations)
B^+ = NTT_omega(reflections)
B^- = NTT_omega^{-1}(reflections)
```

For each two-dimensional irrep `rho_j`, the matrix coefficient is assembled as:

```text
1/(2n) * [[A^+[j], B^-[j]],
          [B^+[j], A^-[j]]]
```

The inverse FFT reverses this packing. The one-dimensional coefficients recover
the `j = 0` cyclic frequencies, and, for even `n`, the `j = n/2` frequencies.
The two-dimensional matrices recover the paired frequencies `j` and `n-j`.
Once the full `A^+` and `B^+` spectra have been rebuilt, two inverse NTTs give
back the rotation and reflection coefficient vectors.

## Group Algebra Multiplication

Elements of the group algebra are represented by the same two arrays:

```text
x = sum_k rotations[k] r^k + sum_k reflections[k] s r^k
```

The package provides both a quadratic reference product and an FFT product:

```python
from fft_dihedral import (
    DEFAULT_MODULUS,
    dihedral_multiply_fft,
    dihedral_multiply_naive,
    root_of_unity,
)

n = 16
omega = root_of_unity(n, DEFAULT_MODULUS)
lhs_rotations = [1] * n
lhs_reflections = [2] * n
rhs_rotations = [3] * n
rhs_reflections = [4] * n

fast = dihedral_multiply_fft(
    lhs_rotations,
    lhs_reflections,
    rhs_rotations,
    rhs_reflections,
    DEFAULT_MODULUS,
    omega,
)
slow = dihedral_multiply_naive(
    lhs_rotations,
    lhs_reflections,
    rhs_rotations,
    rhs_reflections,
    DEFAULT_MODULUS,
)
assert fast == slow
```

Because the transform is normalized by `1 / |D_{2n}|`, multiplication in
Fourier space is

```text
(x y)^hat(rho) = |D_{2n}| xhat(rho) yhat(rho).
```

So the FFT product computes two transforms, multiplies each scalar or matrix
block with the extra factor `2n`, and then applies the inverse dihedral FFT.

## 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 `n`th root of unity.
- `gcd(2n, p) = 1`, so the normalization by `1/(2n)` is defined.

The default field is `GF(2013265921)`, where

```text
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:

```python
from fft_dihedral import root_of_unity

omega = root_of_unity(16, 97)
```

CLI verification over a non-default prime:

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

You can also pass an explicit root:

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

## Verify

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

## Benchmark

```bash
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
fft-dihedral bench-mul --min-exp 4 --max-exp 12 --repetitions 5 --naive-limit 512
```

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.

The `bench-mul` command compares group-algebra multiplication by FFT against
the direct quadratic product. The fast path computes two forward dihedral FFTs,
multiplies the Fourier blocks, and applies one inverse dihedral FFT.

## Plot

Install the plotting extra:

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

Then generate PNG and SVG timing plots:

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

## Limitations

- 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.
