Subset sum pseudorandom numbers: fast generation and distribution

Abstract

We show how to accelerate the subset sum pseudorandom number generator with arbitrary weights. Some special choices of weights speed up the naive usage of this generator without losing the property of uniform distribution which has recently been established in the general case. Our results confirm that this generator can be useful for both cryptographic and Quasi Monte Carlo applications.

Keywords

• pseudorandom numbers
• subset sum problem
• knapsack problem
• exponential sums