Structure of pseudorandom numbers derived from Fermat quotients

Zhixiong Chen; Alina Ostafe; Arne Winterhof

doi:10.1007/978-3-642-13797-6_6

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 proceeding › Conference 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 language	English
Title of host publication	Arithmetic of finite fields
Subtitle of host publication	third international workshop, WAIFI 2010, proceedings
Editors	M. Anwar Hasan, Tor Helleseth
Place of Publication	Berlin; Heidelberg
Publisher	Springer, Springer Nature
Pages	73-85
Number of pages	13
ISBN (Print)	9783642137969
DOIs	https://doi.org/10.1007/978-3-642-13797-6_6
Publication status	Published - 2010
Externally published	Yes
Event	3rd International Workshop on Arithmetic of Finite Fields - Istanbul, Turkey Duration: 27 Jun 2010 → 30 Jun 2010

Publication series

Name	Lecture Notes in Computer Science
Publisher	Springer
Volume	6087
ISSN (Print)	0302-9743

Conference

Conference	3rd International Workshop on Arithmetic of Finite Fields
Country	Turkey
City	Istanbul
Period	27/06/10 → 30/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

Access to Document

10.1007/978-3-642-13797-6_6

Cite this

Chen, Z., Ostafe, A., & Winterhof, A. (2010). Structure of pseudorandom numbers derived from Fermat quotients. In M. A. Hasan, & T. Helleseth (Eds.), Arithmetic of finite fields: third international workshop, WAIFI 2010, proceedings (pp. 73-85). (Lecture Notes in Computer Science; Vol. 6087). Berlin; Heidelberg: Springer, Springer Nature. https://doi.org/10.1007/978-3-642-13797-6_6

@inproceedings{c05d99c442e14b0383762f67ed4a6c6f,

title = "Structure of pseudorandom numbers derived from Fermat quotients",

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.",

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",

author = "Zhixiong Chen and Alina Ostafe and Arne Winterhof",

year = "2010",

doi = "10.1007/978-3-642-13797-6_6",

language = "English",

isbn = "9783642137969",

series = "Lecture Notes in Computer Science",

publisher = "Springer, Springer Nature",

pages = "73--85",

editor = "Hasan, {M. Anwar} and Tor Helleseth",

booktitle = "Arithmetic of finite fields",

address = "United States",

}

Chen, Z, Ostafe, A & Winterhof, A 2010, Structure of pseudorandom numbers derived from Fermat quotients. in MA Hasan & T Helleseth (eds), Arithmetic of finite fields: third international workshop, WAIFI 2010, proceedings. Lecture Notes in Computer Science, vol. 6087, Springer, Springer Nature, Berlin; Heidelberg, pp. 73-85, 3rd International Workshop on Arithmetic of Finite Fields, Istanbul, Turkey, 27/06/10. https://doi.org/10.1007/978-3-642-13797-6_6

Structure of pseudorandom numbers derived from Fermat quotients. / Chen, Zhixiong; Ostafe, Alina; Winterhof, Arne.

Arithmetic of finite fields: third international workshop, WAIFI 2010, proceedings. ed. / M. Anwar Hasan; Tor Helleseth. Berlin; Heidelberg : Springer, Springer Nature, 2010. p. 73-85 (Lecture Notes in Computer Science; Vol. 6087).

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

TY - GEN

T1 - Structure of pseudorandom numbers derived from Fermat quotients

AU - Chen, Zhixiong

AU - Ostafe, Alina

AU - Winterhof, Arne

PY - 2010

Y1 - 2010

N2 - 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.

AB - 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.

KW - Fermat quotients

KW - finite fields

KW - pseudorandom sequences

KW - exponential sums

KW - discrepancy

KW - well-distribution measure

KW - correlation measure

KW - linear complexity

KW - lattice test

KW - LINEAR COMPLEXITY PROFILE

KW - BINARY SEQUENCES

KW - LATTICE PROFILE

KW - GENERATORS

U2 - 10.1007/978-3-642-13797-6_6

DO - 10.1007/978-3-642-13797-6_6

M3 - Conference proceeding contribution

SN - 9783642137969

T3 - Lecture Notes in Computer Science

SP - 73

EP - 85

BT - Arithmetic of finite fields

A2 - Hasan, M. Anwar

A2 - Helleseth, Tor

PB - Springer, Springer Nature

CY - Berlin; Heidelberg

ER -