The M4RIE library for dense linear algebra over small fields with even characteristic. We describe algorithms and implementations for linear algebra with dense matrices over 𝔽 2 e for 2≤e≤10. Our main contributions are: (1) a specialisation of precomputation tables to 𝔽 2 e , called Newton-John tables in this work, to avoid scalar multiplications in Gaussian elimination and matrix multiplication, (2) an efficient implementation of Karatsuba-style multiplication for matrices over extension fields of 𝔽 2 and (3) a description of an open-source library – called M4RIE – providing the fastest known implementation of dense linear algebra over 𝔽 2 e with 2≤e≤10.
Keywords for this software
References in zbMATH (referenced in 3 articles , 1 standard article )
Showing results 1 to 3 of 3.
- Quedenfeld, Frank-M.; Wolf, Christopher: Advanced algebraic attack on Trivium (2016)
- Jeannerod, Claude-Pierre; Pernet, Clément; Storjohann, Arne: Rank-profile revealing Gaussian elimination and the CUP matrix decomposition (2013)
- Albrecht, Martin R.: The M4RIE library for dense linear algebra over small fields with even characteristic (2012)