<h1 align="center">libfqfft</h1> <h4 align="center">C++ library for FFTs in Finite Fields</h4>

libfqfft is a C++ library for Fast Fourier Transforms (FFTs) in finite fields with multithreading support (via OpenMP). The library is developed by [SCIPR Lab] and contributors (see [AUTHORS] file) and is released under the MIT License (see [LICENSE] file). The library provides functionality for fast multipoint polynomial evaluation, fast polynomial interpolation, and fast computation of Lagrange polynomials. Check out the Performance section for memory, runtime, and field operation profiling data.

Directory structure
Introduction
Background
Domains
Performance
Build guide
Testing
Profiling
Tutorials
References

Directory structure

The directory structure is as follows:

libfqfft: C++ source code, containing the following modules:
- evaluation_domain: declaration of interfaces for evaluation domains
- kronecker_substitution: Kronecker substitution for polynomial multiplication
- polynomial_arithmetic: polynomial arithmetic and extended GCD
- profiling: functionality to profile running time, space usage, and number of field operations
- tests: collection of GTests
- tools: tools for evaluation domains
depends: dependency libraries
tutorials: tutorials for getting started with libfqfft

Introduction

This library implements Fast Fourier Transform (FFT) for finite fields, built to be flexible for a variety of software applications. The implementation has support for fast evaluation/interpolation, by providing FFTs and Lagrange-coefficient computations for various domains. These include the standard radix-2 FFT, along with the arithmetic sequence and geometric sequence. The library has multicore support using OpenMP for parallelized computations, where applicable.

Check out the Tutorials section for examples with our high-level API.

Background

There is currently a variety of algorithms for computing the Fast Fourier Transform (FFT) over the field of complex numbers. For this situation, there exists many libraries, such as FFTW, that have been rigorously developed, tested, and optimized. Our goal is to use these existing techniques and develop novel implementations to address the more interesting case of FFT in finite fields. We will see that in many instances, these algorithms can be used for the case of finite fields, but the construction of FFT in finite fields remains, in practice, challenging.

Consider a finite field F with 2^m elements. We can define a discrete Fourier transform by choosing a 2^m − 1 root of unity ω ∈ F. Operating over the complex numbers, there exists a variety of FFT algorithms, such as the Cooley-Tukey algorithm along with its variants, to choose from. And in the case that 2^m - 1 is prime - consider the Mersenne primes as an example - we can turn to other algorithms, such as Rader's algorithm and Bluestein's algorithm. In addition, if the domain size is an extended power of two or the sum of powers of two, variants of the radix-2 FFT algorithms can be employed to perform the computation.

However, in a finite field, there may not always be a root of unity. If the domain size is not as mentioned, then one can consider adjoining roots to the field. Although, there is no guarantee that adjoining such a root to the field can render the same performance benefits, as it would produce a significantly larger structure that could cancel out benefits afforded by the FFT itself. Therefore, one should consider other algorithms which continue to perform better than the naïve evaluation.

Domains

Given a domain size, the library will determine and perform computations over the best-fitted domain. Ideally, it is desired to perform evaluation and interpolation over a radix-2 FFT domain, however, this may not always be possible. Thus, the library provides the arithmetic and geometric sequence domains as fallback options, which we show to perform better than naïve evaluation.

| | Basic Radix-2 | Extended Radix-2 | Step Radix-2 | Arithmetic Sequence | Geometric Sequence | |---------------|:-------------:|:----------------:|:------------:|:--------------------:|:------------------:| | Evaluation | O(n log n) | O(n log n) | O(n log n) | M(n) log(n) + O(M(n)) | 2M(n) + O(n) | | Interpolation | O(n log n) | O(n log n) | O(n log n) | M(n) log(n) + O(M(n)) | 2M(n) + O(n) |

Radix-2 FFTs

The radix-2 FFTs are comprised of three domains: basic, extended, and step radix-2. The radix-2 domain implementations make use of pseudocode from [CLRS 2n Ed, pp. 864].

Basic radix-2 FFT

The basic radix-2 FFT domain has size m = 2^k and consists of the m-th roots of unity. The domain uses the standard FFT algorithm and inverse FFT algorithm to perform evaluation and interpolation. Multi-core support includes parallelizing butterfly operations in the FFT operation.

Extended radix-2 FFT

The extended radix-2 FFT domain has size m = 2^(k + 1) and consists of the m-th roots of unity, union a coset of these roots. The domain performs two basic_radix2_FFT operations for evaluation and interpolation in order to account for the extended domain size.

Step radix-2 FFT

The step radix-2 FFT domain has size m = 2^k + 2^r and consists of the 2^k-th roots of unity, union a coset of 2^r-th roots of unity. The domain performs two basic_radix2_FFT operations for evaluation and interpolation in order to account for the extended domain size.

Arithmetic sequence

The arithmetic sequence domain is of size m and is applied for more general cases. The domain applies a basis conversion algorithm between the monomial and the Newton bases. Choosing sample points that form an arithmetic progression, a_i = a_1 + (i - 1)*d, allows for an optimization of computation over the monomial basis, by using the special case of Newton evaluation and interpolation on an arithmetic progression, see [BS05].

Geometric sequence

The geometric sequence domain is of size m and is applied for more general cases. The domain applies a basis conversion algorithm between the monomial and the Newton bases. The domain takes advantage of further simplications to Newton evaluation and interpolation by choosing sample points that form a geometric progression, a_n = r^(n-1), see [BS05].

Performance

We now discuss performance data of the library in terms of number of field operations, running time, and memory usage, across all evaluation domains.

Machine Specification: The following benchmark data was obtained on a 64-bit Intel i7 Quad-Core machine with 16GB RAM (2x8GB) running Ubuntu 14.04 LTS. The code is compiled using g++ 4.8.4.

Architecture:          x86_64
CPU op-mode(s):        32-bit, 64-bit
Byte Order:            Little Endian
CPU(s):                8
On-line CPU(s) list:   0-7
Thread(s) per core:    1
Core(s) per socket:    2
Socket(s):             4
NUMA node(s):          1
Vendor ID:             GenuineIntel
CPU family:            6
Model:                 94
Stepping:              3
CPU MHz:               4008.007
BogoMIPS:              8016.01
Virtualization:        VT-x
L1d cache:             32K
L1i cache:             32K
L2 cache:              256K
L3 cache:              8192K
NUMA node0 CPU(s):     0-7

Runtime

Memory

Field operations

Build guide

The library has the following dependencies:

The library has been tested on Linux, but it is compatible with Windows and Mac OS X. (Nevertheless, memory profiling works only on Linux machines.)

Installation

On Ubuntu 14.04 LTS:

sudo apt-get install build-essential git libboost-all-dev cmake libgmp3-dev libssl-dev libprocps3-dev pkg-config gnuplot-x11

Compilation

Fetch dependencies from their GitHub repos:

git submodule init && git submodule update

To compile, starting at the project root directory, create the Makefile:

mkdir build && cd build
cmake ..

For macOS compilation, as libprocps is not compatible, create the Makefile with:

cmake .. -DWITH_PROCPS=OFF

Options

The following flags change the behavior of the compiled code:

cmake .. -DCMAKE_INSTALL_PREFIX=/install/path Specifies the install location f

Libfqfft

Install / Use

README

Table of contents