Bitslicing and the Method of Four Russians Over Larger Finite Fields

2009/01/11 by Tomas Boothby, Tomas J. Boothby, Boothby, Tomas J. +3 · 1 citation
Computer Science · Mathematics · #Coding theory and cryptography #FOS: Computer and information sciences #Geometric and Algebraic Topology #Mathematical Software (cs.MS) #Polynomial and algebraic computation #cs.MS

paper · pdf · doi:10.48550/arxiv.0901.1413

arxiv created 2009/01/11 · openalex publication_date 2009/01/11 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We present a method of computing with matrices over very small finite fields of size larger than 2. Specifically, we show how the Method of Four Russians can be efficiently adapted to these larger fields, and introduce a row-wise matrix compression scheme that both reduces memory requirements and allows one to vectorize element operations. We also present timings which confirm the efficiency of these methods and exceed the speed of the fastest implementations the authors are aware of.

Cited by

• Fast Matrix Multiplication and Symbolic Computation
• Simultaneous modular reduction and Kronecker substitution for small finite fields

Related

• Efficient dot product over word-size finite fields
• Computable Compressed Matrices
• The M4RIE library for dense linear algebra over small fields with even characteristic
• Multiword matrix multiplication over large finite fields in floating-point arithmetic
• A parallel algorithm for Gaussian elimination over finite fields