Near Quadratic Matrix Multiplication Modulo Composites

2003/01/08 by Vince Grolmusz, Grolmusz, Vince
Computer Science · #Computational Complexity (cs.CC) #Discrete Mathematics (cs.DM) #F.1.3 #F.2.1 #FOS: Computer and information sciences #G.1.3 #cs.CC #cs.DM

paper · pdf · doi:10.48550/arxiv.cs/0301004

Prelimanary version, 6 pages

arxiv created 2003/02/04 · arxiv updated 2009/11/30

Abstract

We show how one can use non-prime-power, composite moduli for computing representations of the product of two n× n matrices using only n^2+o(1) multiplications.

Related

• Defying Dimensions Mod 6
• Computing Elementary Symmetric Polynomials with a Sublinear Number of Multiplications
• Compressed Modular Matrix Multiplication
• A new quadratic-time number-theoretic algorithm to solve matrix multiplication problem
• Decomposition of an integer as the sum of two cubes to a fixed modulus