Metadata-Version: 2.4
Name: fft-dihedral
Version: 0.1.0
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).

## Install

From PyPI, once published:

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

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

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

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:

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