How ekaragoz77/polyinv works
Project type and purpose
• This is an open-source C library plus a set of command-line benchmarking/testing tools for implementing and comparing constant-time polynomial inversion algorithms in GF(2)[x]/(x^r−1) for post-quantum cryptography.
• Core deliverables:
• A reusable library (“gf2x”) providing polynomial arithmetic (add, multiply, square, reduction, random generation, printing)
• Five inversion algorithm modules (BYI, FLT, CEA, TYT, SAC) each in its own .c file
• A benchmarking harness (bench.c/.h) to measure cycle-counts and function-call counts
• Three test programs (test_inv.c, test_count.c, test_speed.c) invoked by shell scripts for correctness, call-counting, and speed tests
File structure
• Top‐level build & metadata: Makefile, .gitignore, LICENSE, AUTHORS
• Configuration headers: config.h (build switches), params.h (predefined primes & EXTDEG macro)
• Library headers: gf2x.h (API), bench.h (benchmark API)
• Core arithmetic modules (gf2x_add.c, gf2x_mul.c, gf2x_sqr.c, gf2x_red.c, gf2x_base.c, bench.c)
• Inversion modules: gf2x_inv_byi.c, gf2x_inv_flt.c, gf2x_inv_cea.c, gf2x_inv_sac.c, gf2x_inv_tyt.c
• Utility / support: gf2x_print.c, gf2x_rand.c
• Test programs: test_inv.c, test_count.c, test_speed.c
• Runner scripts: run_test_inv.sh, run_test_count.sh, run_test_speed.sh
README for additional insights
• Describes each inversion algorithm’s underlying math (Extended Euclidean vs FLT variants)
• Explains the use of EXTDEG for polynomial degree and lists primes in params.h
• Documents how Makefile orchestrates compilation (GCC + -O3 + march=native)
• Clarifies that benchmark metrics include cycle-counts and # of low-level calls
Components
a. Core Library Layer (“gf2x”):
• Polynomial arithmetic sub-modules (add, mul, sqr, red, base)
• Utility sub-modules (rand, print)
b. Inversion Algorithm Layer:
• Five algorithm modules, each depending on the arithmetic API in gf2x.h
c. Benchmarking Layer:
• bench.c/.h providing timing (rdtsc) and function-call instrumentation
d. Test Harness Layer:
• test_inv (correctness), test_count (call counts), test_speed (performance)
• Each test program links against core library + bench harness + chosen inversion modules
e. Orchestration Layer:
• Shell scripts (run_test_*.sh) that invoke make and then run the corresponding test binary over all configured primes and EXTDEG values
f. Build & Config Layer:
• Makefile (compilation rules, dependency graph)
• config.h & params.h (macro flags, prime parameters)
Relationships and interactions
• Test scripts → call Test programs
• Test programs → link to and call:
• Benchmark harness (bench API) for timing/counters
• Inversion modules → which call core arithmetic APIs
• Core arithmetic modules → may call lower‐level base operations and utilities
• Makefile coordinates compiling all .c files into static library or object files, then linking tests
Architectural patterns & design principles
• Layered modular design: clear separation between (1) arithmetic kernel, (2) inversion strategies, (3) benchmarking instrumentation, (4) test drivers, (5) orchestration scripts
• Single-responsibility modules: each .c file implements one algorithm or one group of operations
• Extensibility point: new inversion algorithms or new primes can be added by creating a new .c file and updating params.h/scripts
Detailed capture of essential elements
• Every .c/.h module group is represented, or aggregate small utilities where appropriate
• Clearly separate compile-time configuration (Makefile, headers) from runtime flow (scripts → binaries → library calls)
• Avoid clutter by grouping related modules (e.g., all gf2x_*.c under “Core Arithmetic Library”) but keep algorithm modules separate