Multiplicative character sums of Fermat quotients and pseudorandom sequences
- PDF / 116,109 Bytes
- 8 Pages / 595 x 842 pts (A4) Page_size
- 27 Downloads / 206 Views
MULTIPLICATIVE CHARACTER SUMS OF FERMAT QUOTIENTS AND PSEUDORANDOM SEQUENCES Domingo Gomez1 and Arne Winterhof2 1
2
University of Cantabria, Avd. de los Castros s/n, Santander, Spain E-mail: [email protected]
Johann Radon Institute for Computational and Applied Mathematics, Austrian Academy of Sciences, Altenberger Straße 69, A-4040 Linz, Austria E-mail: [email protected] (Received June 7, 2010; Accepted August 18, 2010) [Communicated by Andr´ as S´ ark¨ ozy]
Abstract We prove a bound on sums of products of multiplicative characters of shifted Fermat quotients modulo p. From this bound we derive results on the pseudorandomness of sequences of modular discrete logarithms of Fermat quotients modulo p: bounds on the well-distribution measure, the correlation measure of order ℓ, and the linear complexity.
1. Introduction For a prime p and an integer u with gcd(u, p) = 1, the Fermat quotient qp (u) modulo p is defined as the unique integer with qp (u) ≡
up−1 − 1 mod p, p
0 ≤ qp (u) ≤ p − 1,
and we define qp (u) = 0 if u ≡ 0 mod p. There are several results which involve the distribution and structure of Fermat quotients qp (u) modulo p and they have numerous applications in computational and algebraic number theory, see e.g. [1], [3], [5], [6], [7], [8], [13], [15] and references therein. In particular, Shparlinski [15] Mathematics subject classification numbers: 11T24; 11K45, 11K36, 11T71, 94A55. Key words and phrases: Fermat quotients, finite fields, character sums, pseudorandom sequences, discrete logarithm, correlation measure, linear complexity. 0031-5303/2012/$20.00 c Akad´emiai Kiad´o, Budapest
Akad´ emiai Kiad´ o, Budapest Springer, Dordrecht
162
D. GOMEZ and A. WINTERHOF
proved a bound on character sums for any nontrivial multiplicative character ψ, which can be easily extended to N −1 X
2
ψ(qp (au + b)) ≪ N 1−1/ν p(5ν+1)/(4ν ) (log p)1/ν , 1 ≤ N ≤ p2 ,
(1)
u=0
for any integers a, b with gcd(a, p2 ) 6= p2 , where U ≪ V is equivalent to the assertion that the inequality |U | ≤ cV holds for some constant c > 0 which depends only on the parameter ν or is absolute otherwise. Here we study the following multiplicative character sums: N −1 X
ψ1 (qp (u + d1 )) · · · ψℓ (qp (u + dℓ )),
1 ≤ N ≤ p2 ,
u=0
with nontrivial multiplicative characters ψ1 , . . . , ψℓ modulo p and lags 0 ≤ d1 < d2 < · · · < dℓ ≤ p2 − 1. We prove a bound on these character sums of order of magnitude n ℓN o max 1/3 , ℓp3/2 log p p in Section 2. Besides standard arguments, the proof is based on a result of HeathBrown [8, Lemma 4] on the number of solutions of the congruences p−1 i X u i=1
i
≡ c mod p,
0 ≤ u ≤ p − 1.
We apply this character sum bound to derive results on the pseudorandomness of sequences (eu ) of discrete logarithms modulo a divisor m ≥ 2 of p − 1 of Fermat quotients modulo p defined by exp(2πieu /m) = χ(qp (u)), 0 ≤ eu < m
if qp (u) 6≡ 0 mod p
(2)
and eu = 0 otherwise, where χ is a fixed multiplicative character modulo p of order m. We prove bounds on the well-distribution measure, correla
Data Loading...
