Deterministic linear-time algorithm for modular subset sum problem
Practical Deterministic Linear-Time Modular Subset Sum
Data Structures and Algorithms
Summary
Finding all possible sums from given numbers but wrapped around a modulo can be tricky. This paper presents a method that always gives the exact answers quickly and in a predictable amount of time. The authors use clever math and data organization to handle these sums efficiently without complex tools. Their approach works fast in practice, making it easier to find specific sums and witnesses.
What this means in practice
- •For software engineers: Improve algorithms used in cryptography and optimization by efficiently solving modular subset sum problems deterministically and quickly.
- •For algorithm developers: Provide a practical tool for designing systems that require fast modular arithmetic computations with guaranteed deterministic behavior.
Authors
Phuoc Dinh Le, Kha Le
Abstract
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.