Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR26-130 | 1st August 2026 16:54

Optimal Bitwise Pseudorandom Generators for Modular Sums Modulo $2^{t}\cdot p^{k}$

RSS-Feed




TR26-130
Authors: Gonen Krak
Publication: 1st August 2026 17:08
Downloads: 29
Keywords: 


Abstract:

We study pseudorandom bit generators for Boolean linear sums modulo a fixed
integer $M$. A distribution $X\in\{0,1\}^n$ $\varepsilon$-fools these tests if, for
every $a\in\mathbb{Z}_M^n$, the distribution of
\[
\sum_{i=1}^n a_iX_i \pmod M
\]
is $\varepsilon$-close in statistical distance to the corresponding distribution
under independent uniform bits.

Lovett, Reingold, Trevisan, and Vadhan constructed generators with optimal
seed length for every fixed prime-power modulus. We extend this result to
every fixed modulus of the form
\[
M=2^{t}\cdot p^{k},
\]
where $t,k\ge 0$ and $p$ an odd prime. Specifically, we give an
explicit generator with seed length
\[
O_M\!\left(\log n+\log\frac{1}{\varepsilon}\right),
\]
which is optimal up to the constant depending on $M$.

Our main contribution is a modulus-doubling reduction that transforms any
generator fooling Boolean linear sums modulo $m$ into one fooling such sums
modulo $2m$, while preserving the optimal asymptotic seed length.



ISSN 1433-8092 | Imprint