Classical long arithmetic and Galois fields realisation in C.
- Base for all numbers is machine word(64 or 32 bits).
- Several methods for modular exponentation are supported. Mod operation is implemented using fast Barret reduction.
- Library works with any-length numbers. Number length is bounded only with amount of memory, so one could allocate 128, 256, 512, 1024, 2048, 4096 bit-numbers without recompilation of library.
- Library provides module for operating in finite Galois fields of characteristic 2. Polynomial and Normal basises are supported, however normal basis is bit slowly than polynomial.
- Library provides three algorithms for multiplication: School algorithm that runs at O(n^2), Karatsuba's recursive algorithm - O(n^log3) and Schönhage-Strassen's algorithm - O(n*log(n)*log(log(n))). By default inner functions such as powering use common school multiplication, in order to change this behavior call
set_l_mul_funcwith appropriate backend multiplication function. Schönhage-Strassen's algorithm implementation is based on https://hal.inria.fr/inria-00126462v1. It accepts only numbers of equal length in format N = M * 2^k, where K = 2^k is number of blocks of Mbit words input numbers are split in the decompose stage of algorithm. In current implementation additional condition must hold for M: it must be divisible by ARCH/2, where ARCH is the size of machine word.