Practical Deterministic Linear-Time Modular Subset Sum
In the authors' words
We give a deterministic algorithm for exact modular subset sum that, for every modulus m, computes all reachable residues and one requested witness in O(m) time and O(m) auxiliary words. The input is a compact list of distinct residues with multiplicities, and the word-RAM supports constant-time modular arithmetic. The algorithm represents reachable residues as intervals along cycles of repeated addition, charging work on partial cycles to newly reached residues. Processing prime factors in increasing order keeps the cost of rebuilding and changing cycles linear. A classical theorem on subset sums of distinct invertible residues bounds the number of boundary lists by O(m^(3/4)); together they contain O(m) interval endpoints. Comparison sorting the short lists and radix sorting the long ones then takes O(m) total time. The algorithm is fast in practice, using arrays and interval lists rather than heavy data structures.
Appeared: Monday, September 28. arXiv. Preprint, not yet peer-reviewed.
Authors' comment: 18 pages, 4 figures