Suwako 🐸

Optimized Depth Modular Reduction over $GF(2^m)$ for trinomials

This repository contains the Proof-of-Concept (PoC) implementation for the Suwako algorithm.

🚀 Key Features

• Logarithmic Depth: Breaks the linear dependency of traditional LFSRs, achieving $O(\log m)$ folding depth.
• Parameter Agility: Supports arbitrary trinomials (runtime variable $k$) with a unified, branch-free datapath.
• Compactness: Core reduction logic is implemented in < 10 lines of Python.

📄 Paper

For the theoretical proof complexity/depth analysis, please refer to our paper:

Suwako: A Logarithmic-Depth Modular Reduction for Arbitrary Trinomials over $\mathbb{F}_{2^m}$ without Pre-computation > Read the Paper (PDF)

🛠️ Usage

Run the automated testbench (validates against standard LFSR ground truth):

# to check correctness
python poc.py
# to benchmark
python bench.py