We study pseudorandom bit generators for Boolean linear sums modulo a fixed
integer $M$. A source $X \in \{0,1\}^n$ succeeds with error
$\varepsilon$ if, for every $a \in \mathbb{Z}_M^n$, the residue
\[
\sum_{i=1}^n a_i X_i \pmod M
\]
is $\varepsilon$-close in statistical distance to the corresponding residue
under independent uniform bits. Lovett, Reingold, Trevisan, and Vadhan obtained
the optimal seed length for prime-power moduli. We prove the same bound for
every fixed modulus:
\[
O_M\left(\log n + \log \frac{1}{\varepsilon}\right).
\]

The proof builds the generator in stages. It keeps two quantities separate:
the prime field $\mathbb{F}_p$ containing the generator's output, and the
modulus $m$ used by the test. A state $(p,m)$ means that we have a PRG
on $\mathbb{F}_p^n$ that fools every modulus-$m$ phase whose coordinates
contribute separately.

We use two steps to move between states. The first step,
$\mathrm{LIFT}_p$, changes the modulus from $m$ to $pm$. The second
step, $\mathrm{TRANSFER}_{r \to p}$, changes the alphabet from
$\mathbb{F}_r$ to a smaller field $\mathbb{F}_p$.

Starting from the trivial modulus $1$, we process the prime factors of $M$
until we reach the Boolean state $(2,M)$.

Improved Section 2 Explanation

We study pseudorandom bit generators for Boolean linear sums modulo a fixed
integer $M$. A source $X \in \{0,1\}^n$ succeeds with error
$\varepsilon$ if, for every $a \in \mathbb{Z}_M^n$, the residue
\[
\sum_{i=1}^n a_i X_i \pmod M
\]
is $\varepsilon$-close in statistical distance to the corresponding residue
under independent uniform bits. Lovett, Reingold, Trevisan, and Vadhan obtained
the optimal seed length for prime-power moduli. We prove the same bound for
every fixed modulus:
\[
O_M\left(\log n + \log \frac{1}{\varepsilon}\right).
\]

The proof builds the generator in stages. It keeps two quantities separate:
the prime field $\mathbb{F}_p$ containing the generator's output, and the
modulus $m$ used by the test. A state $(p,m)$ means that we have a PRG
on $\mathbb{F}_p^n$ that fools every modulus-$m$ phase whose coordinates
contribute separately.

We use two steps to move between states. The first step,
$\mathrm{LIFT}_p$, changes the modulus from $m$ to $pm$. The second
step, $\mathrm{TRANSFER}_{r \to p}$, changes the alphabet from
$\mathbb{F}_r$ to a smaller field $\mathbb{F}_p$.

Starting from the trivial modulus $1$, we process the prime factors of $M$
until we reach the Boolean state $(2,M)$.

Rewrote several lemmas to be easier to understand

We study pseudorandom bit generators for Boolean linear sums modulo a fixed
integer $M$. A source $X \in \{0,1\}^n$ succeeds with error
$\varepsilon$ if, for every $a \in \mathbb{Z}_M^n$, the residue
\[
\sum_{i=1}^n a_i X_i \pmod M
\]
is $\varepsilon$-close in statistical distance to the corresponding residue
under independent uniform bits. Lovett, Reingold, Trevisan, and Vadhan obtained
the optimal seed length for prime-power moduli. We prove the same bound for
every fixed modulus:
\[
O_M\left(\log n + \log \frac{1}{\varepsilon}\right).
\]

The proof builds the generator in stages. It keeps two quantities separate:
the prime field $\mathbb{F}_p$ containing the generator's output, and the
modulus $m$ used by the test. A state $(p,m)$ means that we have a PRG
on $\mathbb{F}_p^n$ that fools every modulus-$m$ phase whose coordinates
contribute separately.

We use two steps to move between states. The first step,
$\mathrm{LIFT}_p$, changes the modulus from $m$ to $pm$. The second
step, $\mathrm{TRANSFER}_{r \to p}$, changes the alphabet from
$\mathbb{F}_r$ to a smaller field $\mathbb{F}_p$.

Starting from the trivial modulus $1$, we process the prime factors of $M$
until we reach the Boolean state $(2,M)$.

Fixed title

We study pseudorandom bit generators for Boolean linear sums modulo a fixed
integer $M$. A source $X \in \{0,1\}^n$ succeeds with error
$\varepsilon$ if, for every $a \in \mathbb{Z}_M^n$, the residue
\[
\sum_{i=1}^n a_i X_i \pmod M
\]
is $\varepsilon$-close in statistical distance to the corresponding residue
under independent uniform bits. Lovett, Reingold, Trevisan, and Vadhan obtained
the optimal seed length for prime-power moduli. We prove the same bound for
every fixed modulus:
\[
O_M\left(\log n + \log \frac{1}{\varepsilon}\right).
\]

The proof builds the generator in stages. It keeps two quantities separate:
the prime field $\mathbb{F}_p$ containing the generator's output, and the
modulus $m$ used by the test. A state $(p,m)$ means that we have a PRG
on $\mathbb{F}_p^n$ that fools every modulus-$m$ phase whose coordinates
contribute separately.

We use two steps to move between states. The first step,
$\mathrm{LIFT}_p$, changes the modulus from $m$ to $pm$. The second
step, $\mathrm{TRANSFER}_{r \to p}$, changes the alphabet from
$\mathbb{F}_r$ to a smaller field $\mathbb{F}_p$.

Starting from the trivial modulus $1$, we process the prime factors of $M$
until we reach the Boolean state $(2,M)$.

Improved proof structure, readability, terminology and found simpler proofs for several lemmas. The proof still involves quite heavy notation, but this seems intrinsic to the current proof ideas. New revisions will be made upon received presentation-related feedback or simplification ideas.

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 remove the restriction to
prime powers: for \emph{every} fixed modulus $M\ge2$ 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$.

The proof rests on decoupling two parameters that previous arguments had tied
together: the prime alphabet over which the pseudorandom source is defined,
and the modulus of the test. We work with \emph{local phase classes}, which
are closed under arbitrary reparameterisation of each coordinate, and we show
that the construction can move downward between prime alphabets. Two operations
suffice: over the alphabet $\F_p$, taking $p$ multiplicative derivatives
removes one factor of $p$ from the modulus, which lets a sequence of $p$
small-bias masks insert that factor; and any surjection $\F_r\to\F_p$, combined with one mask,
transports a generator to a smaller alphabet. Walking the prime factors of $M$
in decreasing order of alphabet assembles the generator, ending over $\F_2$.
The only imported pseudorandomness primitive is explicit small bias over fixed
prime fields.

Revision 2 Update: Extended the result to every fixed modulus (M) by combining the core proof idea with a new alphabet-transfer reduction.

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.