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-10-20}
}