Structure of pseudorandom numbers derived from Fermat quotients

Zhixiong Chen*, Alina Ostafe, Arne Winterhof

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference proceeding contribution

45 Citations (Scopus)

Abstract

We study the distribution of s-dimensional points of Fermat quotients modulo p with arbitrary lags. If no lags coincide modulo p the same technique as in [21] works. However, there are some interesting twists in the other case. We prove a discrepancy bound which is unconditional for s = 2 and needs restrictions on the lags for s > 2. We apply this bound to derive results on the pseudorandomness of the binary threshold sequence derived from Fermat quotients in terms of bounds on the well-distribution measure and the correlation measure of order 2, both introduced by Mauduit and Sarkozy. We also prove a lower bound on its linear complexity profile. The proofs are based on bounds on exponential sums and earlier relations between discrepancy and both measures above shown by Mauduit, Niederreiter and Sarkozy. Moreover, we analyze the lattice structure of Fermat quotients modulo p with arbitrary lags.

Original languageEnglish
Title of host publicationArithmetic of finite fields
Subtitle of host publicationthird international workshop, WAIFI 2010, proceedings
EditorsM. Anwar Hasan, Tor Helleseth
Place of PublicationBerlin; Heidelberg
PublisherSpringer, Springer Nature
Pages73-85
Number of pages13
ISBN (Print)9783642137969
DOIs
Publication statusPublished - 2010
Externally publishedYes
Event3rd International Workshop on Arithmetic of Finite Fields - Istanbul, Turkey
Duration: 27 Jun 201030 Jun 2010

Publication series

NameLecture Notes in Computer Science
PublisherSpringer
Volume6087
ISSN (Print)0302-9743

Conference

Conference3rd International Workshop on Arithmetic of Finite Fields
CountryTurkey
CityIstanbul
Period27/06/1030/06/10

Keywords

  • Fermat quotients
  • finite fields
  • pseudorandom sequences
  • exponential sums
  • discrepancy
  • well-distribution measure
  • correlation measure
  • linear complexity
  • lattice test
  • LINEAR COMPLEXITY PROFILE
  • BINARY SEQUENCES
  • LATTICE PROFILE
  • GENERATORS

Cite this