Distribution of recursive matrix pseudorandom number generator modulo prime powers

DOI10.1090/MCOM/3895arXiv2302.03964OpenAlexW4387937037MaRDI QIDQ6203467FDOQ6203467

Igor E. Shparlinski, László Mérai

Publication date: 28 February 2024

Published in: Mathematics of Computation (Search for Journal in Brave)

Abstract: Given a matrix $Ainmathrm{GL}_d(mathbbZ)$. We study the pseudorandomness of vectors $mathbf{u}_n$ generated by a linear recurrent relation of the form ${\displaystyle }$ mathbf{u}_{n+1} equiv A mathbf{u}_n pmod {p^t}, qquad n = 0, 1, ldots, ${\displaystyle }$ modulo $p^t$ with a fixed prime $p$ and sufficiently large integer $tgeq1$. We study such sequences over very short segments of length which is not accessible via previously used methods. Our technique is based on the method of N. M. Korobov (1972) of estimating double Weyl sums and a fully explicit form of the Vinogradov mean value theorem due to K. Ford (2002). This is combined with some ideas from the work of I. E. Shparlinski (1978) which allows to construct polynomial representations of the coordinates of $mathbf{u}_n$ and control the $p$-adic orders of their coefficients in polynomial representation.

Full work available at URL: https://arxiv.org/abs/2302.03964

zbMATH Keywords

exponential sumsprime powersVinogradov mean value theoremmatrix congruential pseudorandom numbers

Mathematics Subject Classification ID

Irregularities of distribution, discrepancy (11K38) Estimates on exponential sums (11L07) Pseudo-random numbers; Monte Carlo methods (11K45)

Cites Work

• Title not available (Why is that?)
• Sequences, discrepancies and applications
• Title not available (Why is that?)
• On quantum ergodicity for linear maps of the torus.
• Title not available (Why is that?)
• VINOGRADOV'S INTEGRAL AND BOUNDS FOR THE RIEMANN ZETA FUNCTION
• Title not available (Why is that?)
• Proof of the main conjecture in Vinogradov's mean value theorem for degrees higher than three
• Mordell’s exponential sum estimate revisited
• Multilinear exponential sums in prime fields under optimal entropy condition on the sources
• Title not available (Why is that?)
• Nested efficient congruencing and relatives of Vinogradov's mean value theorem
• \(p\)-adic numbers. An introduction
• THE ARITHMETIC THEORY OF QUANTUM MAPS
• On digits of Mersenne numbers
• On the dynamical system generated by the Möbius transformation at prime times
• Distribution of short subsequences of inversive congruential pseudorandom numbers modulo $2^t$
• A Remark on Quantum Ergodicity for CAT Maps
• Equations and Character Sums with Matrix Powers, Kloosterman Sums over Small Subgroups, and Quantum Ergodicity

This page was built for publication: Distribution of recursive matrix pseudorandom number generator modulo prime powers

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6203467)