On discrepancy estimates for pseudorandom vectors constructed by the elliptic curve congruential generator

Abstract

This paper studies the problem of discrepancy estimates for pseudorandom vectors constructed by the elliptic curve congruential generator, particularly in the non-translational case. Two families of results are obtained. First, in a full-coset regime characterized by a relative maximal period condition (RMPC) on an induced one-dimensional linear congruential generator, one proves bounds of type $q^{1/2}/t$ for the discrepancy $D$, the serial discrepancy $D_s$, and, under the corresponding derived RMPC, the non-overlapping discrepancy ${\tilde{D}}_s$. Second, in the general sub-period regime, one reduces bounds for $D$, $D_s$, and ${\tilde{D}}_s$ to estimation of Fourier ${\ell }^1$ masses of admissible index sets attached to one-dimensional linear congruential generators. This isolates the arithmetic bottleneck for further improvement.

30 pages