nmod_mat_mul_u8

For $n = 2$ and $n = 3$ the entries are packed into bits (one bit per entry for $n = 2$, two bit planes for $n = 3$) and multiplied by Strassen–Winograd over the packed matrices with leaves computed by the method of four Russians, unless $A$ has fewer than 64 (for $n = 2$) or 192 (for $n = 3$) rows. For $n \le 16$ the entries are converted to bytes and multiplied by a kernel that replaces each multiplication by a table lookup within a vector register, under Strassen–Winograd when all dimensions are at least 256. For $17 \le n \le 255$ the products are computed by flint_sgemm on blocks of at most $\lfloor (2^{24} - 1)/(n - 1)^2 \rfloor$ columns of $A$, under Strassen–Winograd on bytes when all dimensions are at least 2048, or by a single flint_sgemm when several threads are available, $m, n \ge 256$ and $k (n - 1)^2 < 2^{24}$.

AlgorithmMatrix multiplication modulo small integersHow nmod_mat_mul_u8 multiplies matrices modulo $N \le 255$ with entries in bytes, replacing multiplications by in-register table lookups for $N \le 16$, and with bit-packed Strassen–Winograd and the method of four Russians for $N = 2$ and $N = 3$.

@misc{flint-doc-nmod-mat-nmod-mat-mul-u8,
  author       = {{The FLINT team}},
  title        = {{nmod\_mat\_mul\_u8 (nmod\_mat.h)}},
  howpublished = {FLINT: Fast Library for Number Theory, documentation, version 3.7.0-dev},
  year         = {2026},
  url          = {https://flintlib.org/doc/nmod_mat/nmod_mat_mul_u8.html},
  note         = {Generated 2026-11-02}
}