RNS Montgomery multiplication with AVX512

Standalone C++ template/header code. Benchmarks use Google Benchmark. Inversion with BLST requires BLST with extern "C" modification.

Artifact reviewers: start with ARTIFACT.md (environment, smoke test, parameter generation).

Verify IFMA on a fresh instance:

cat /etc/os-release && uname -r
lscpu | grep -E 'Model name|Flags' | head -5
grep -q avx512ifma /proc/cpuinfo && echo "IFMA ok" || echo "Use fallback build"

Compiler note: AVX-512 IFMA performance depends strongly on the compiler. Newer clang (we used 21.1.0 on the paper host) emits much better IFMA code than distro GCC or older clang on the same CPU. Use scripts/setup_toolchain.sh for paper-comparable timings; older compilers are fine for correctness builds only.

GPU benchmarks are optional; see scripts/README.md.

Install dependencies — Amazon Linux 2023 (paper host):

chmod +x scripts/setup_toolchain.sh
./scripts/setup_toolchain.sh
eval "$(./scripts/setup_toolchain.sh --print)"

Pins clang 21.1.0 and google/benchmark at paper commits; see ARTIFACT.md §2.

Ubuntu:

sudo apt install build-essential libgmp-dev libbenchmark-dev

Build:

cd blst
make
cd ../src
make

Requires AVX-512 IFMA (-mavx512ifma). For integer-simulated vector ops (debugging / machines without IFMA), use make -f Makefile.fallback in src/ — compiles slowly and is not used for performance work.

Quick verification:

chmod +x scripts/smoke_test.sh
./scripts/smoke_test.sh

Use FALLBACK=1 ./scripts/smoke_test.sh without IFMA.

make -C examples
./examples/01_parameter_setup
./examples/02_singular_modmul
./examples/03_sum_of_products
./examples/04_difference_of_products
./examples/05_product_of_sums

See examples/README.md for details. Use make -C examples FALLBACK=1 without IFMA.

Module map and parameter files: src/README.md. Parameter regeneration: ARTIFACT.md § Parameter generation.

VROOM vs BLST is automated in scripts/reproduce_cpu_bench.sh. For arkworks, gnark, zksync, and zkcrypto comparisons, see baselines/README.md and ./baselines/reproduce_baselines.sh.

Paper numbers: AWS c7i.metal-24xl, Amazon Linux 2023, Intel Xeon Platinum 8488C, clang 21.1.0 (~/LLVM-21.1.0-Linux-X64/bin/clang++).

Development: AWS c7i-flex.large on the same AMI family is enough for iteration.

Compiler: GCC and older clang versions are significantly slower than clang 21.x on this codebase — especially on the AVX-512 IFMA path (-mavx512ifma), where LLVM’s backend has improved IFMA instruction selection and scheduling across recent releases. Paper timings use clang 21.1.0 (scripts/setup_toolchain.sh); do not expect to match published ns/op with the Amazon Linux default compiler.

• ./bench_bls12_381 — paper CPU suite. MatrixNoK is the production BLS12-381 configuration (QR “no k” change-base); Matrix (IntRNS2 baseline) rows are also emitted. Parsed tables include both by default; pass --exclude-nok to parse_bench_json.py for Matrix only.

Sample output on c7i.metal-24xl with clang 21.1.0 (MatrixNoK rows; abbreviated):

Running ./bench_bls12_381
...
BM_ModMul_MatrixNoK                        21.8 ns         21.8 ns     ... ModMul_MatrixNoK
BM_BatchModMul_MatrixNoK_1                 21.7 ns         21.7 ns     ... BatchModMul_MatrixNoK_1
...
BM_MillerLoop_MatrixNoK                49888 ns        49888 ns        ... MillerLoop_MatrixNoK
BM_Pairing_RNS_BLST_Inverter_MatrixNoK 128146 ns       128146 ns       ... Pairing_RNS_BLST_Inverter_MatrixNoK

• BM_BatchModMul_N — batch Montgomery multiplication, a*b mod p.
• RNS_BLST_Inverter — uses RNS for FP12 inversion and BLST for FP inversion.
• BM_Inverse — uses an addition chain of length 425 to invert in RNS without BLST dependency (compare to BM_FP12_Inverse_BLST and BM_FP12_Inverse_RNS_BLST)

CPU artifact evaluation does not require a GPU. For paper GPU latency figures:

1. ARTIFACT_GPU.md — environment (Ubuntu + RTX 3090), setup, reproduction commands, claim mapping
2. ./scripts/setup_gpu_deps.sh then ./scripts/reproduce_gpu_latency.sh (runs python3 latency.py)
3. gpu/README.md — CUDA module map

scripts/requirements-gpu.txt pins cuda-python>=12.0,<13 (13.x breaks the imports used by basic_benchmarker.py). If nvcc picks an old default GCC and C++20 JIT fails, set NVCC_CCBIN / CUDAHOSTCXX as documented in ARTIFACT_GPU.md.

MIT. The blst/ subtree keeps its original Apache license and copyright (see blst/LICENSE).

This is research-grade code, demonstrating the speedups of combining AVX512-IFMA, RNS Montgomery, and the BLS12-381 curve. It has not been vetted or audited for security.

Special thanks to Peter Rindal for identifying a bug in the conversion from radix to RNS algorithm, which requires floor rather than ceiling rounding. An updated proof for this case can be found in fix.pdf