On the distribution of the power generator modulo a prime power

JB Friedlander*, JSD Hansen, Igor Shparlinski

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference proceeding contributionpeer-review

Abstract

We study the multidimensional distribution of the power generator of pseudorandom numbers modulo a high power of a fixed prime number. These results complement some recently obtained results about the power generator modulo a product of two distinct primes in which case the generator is of great value for many cryptographic applications. The case of a prime power modulus, although it does not have any immediate cryptography related applications, may still be of interest for other applications which require quality pseudorandom numbers. Moreover, in this case new effects arise which allow us to apply some recent bounds for exponential sums with sparse polynomials to study the multidimensional distribution. In the case of moduli which are the product of two primes such results are known only for power generators with small exponents.

Original languageEnglish
Title of host publicationUnusual applications of number theory
EditorsMB Nathanson
Place of PublicationProvidence
PublisherAMER MATHEMATICAL SOC
Pages71-79
Number of pages9
ISBN (Print)0-8218-2703-0
Publication statusPublished - 2004
EventDIMACS Workshop on Unusual Applications of Number Theory - Piscataway
Duration: 10 Jan 200014 Jan 2000

Publication series

NameDIMACS-Series in Discrete Mathematics and Theoretical Computer Science
PublisherAMER MATHEMATICAL SOC
Volume64
ISSN (Print)1052-1798

Conference

ConferenceDIMACS Workshop on Unusual Applications of Number Theory
CityPiscataway
Period10/01/0014/01/00

Keywords

  • words and phrases
  • exponential sums
  • pseudorandom number generators
  • sparse polynomials
  • CONGRUENTIAL PSEUDORANDOM NUMBERS
  • EXPONENTIAL-SUMS
  • LINEAR COMPLEXITY
  • PARTS

Cite this