K. Lê

Deterministic Linear-Time Modular Subset Sum

We give a deterministic $O(m)$-time algorithm for exact modular subset sum over every modulus $m$. The input gives distinct residues and their multiplicities. The algorithm reports all reachable residues and answers one target query. It returns a witness when the target is reachable. The algorithm uses $O(m)$ auxiliary...