“main” — 2008/8/27 — 17:44 — page 387 — #1
Bull Braz Math Soc, New Series 39(3), 387-399 © 2008, Sociedade Brasileira de Matemática
On a problem of D.H. Lehmer and pseudorandom binary sequences* Huaning Liu and Cundian Yang
Abstract. Let p be an odd prime, and f (x), g(x) ∈ F p [x]. Define en0
=
(
+1, if f (n) ≡ R p (g(n))(mod 2),
−1,
if f (n) 6 ≡ R p (g(n))(mod 2),
where x is the inverse of x modulo p with x ∈ {1, . . . , p − 1}, and R p (x) denotes the unique r ∈ {0, 1, . . . , p − 1} with x ≡ r (mod p). This paper shows that the sequences {en0 } is a “good” pseudorandom binary sequences, and give a generalization on a problem of D.H. Lehmer. Keywords: pseudorandom binary sequence, multiplicative inverse, exponential sum. Mathematical subject classification: 11K45, 11A07, 68Q99.
1 Introduction
Let p be an odd prime number, and let n be the multiplicative inverse of n modulo p such that 1 ≤ n ≤ p − 1 and nn ≡ 1(mod p). D.H. Lehmer [10] asked us to study the case that n and n are of opposite parity. W. Zhang [22] showed that p−1 X
n=1 2-n+n
1=
1 p + O p 1/2 log2 p 2
Received 31 January 2007. *Supported by the National Natural Science Foundation of China under Grant No. 60472068 and No. 10671155; Natural Science Foundation of Shaanxi province of China under Grant No. 2006A04; and the Natural Science Foundation of the Education Department of Shaanxi Province of China under Grant No. 06JK168.
“main” — 2008/8/27 — 17:44 — page 388 — #2
388
HUANING LIU and CUNDIAN YANG
by proving the estimate p−1 X n+n (−1) p 1/2 log2 p. n=1
(1.1)
This means that almost half of the p − 1 integers n ∈ {1, . . . , p − 1} satisfy n ≡ n( mod 2) while the other half satisfy n 6≡ n( mod 2). S.R. Louboutin et al. [15] generalized (1.1) to short sums. For details, they proved that X 8 (−1)n+n ≤ 2 p 1/2 log2 (5 p) + 2, for 1 ≤ M < N < p. π M≤n≤N This shows that the sequence {(−1)n+n } forms a “good” pseudorandom binary sequence. In a series of papers C. Mauduit, J. Rivat and A. Sárközy (partly with other coauthors) studied finite pseudorandom binary sequences E N = {e1 , . . . , e N } ∈ {−1, +1} N .
In particular in [17] C. Mauduit and A. Sárközy first introduced the following measures of pseudorandomness: the well-distribution measure of E N is defined by t−1 X W (E N ) = max ea+ jb , a,b,t j=0
where the maximum is taken over all a, b, t ∈ N with 1 ≤ a ≤ a +(t −1)b ≤ N . The correlation measure of order k of E N is denoted as M X en+d1 en+d2 ∙ ∙ ∙ en+dk , Ck (E N ) = max M,D n=1
where the maximum is taken over all D = (d1 , . . . , dk ) and M with 0 ≤ d1 < ∙ ∙ ∙ < dk ≤ N − M, and the combined (well-distribution-correlation) PR- measure of order k X t Q k (E N ) = max ea+ jb+d1 ea+ jb+d2 ∙ ∙ ∙ ea+ jb+dk a,b,t,D j=0
is defined for all a, b, t, D = (d1 , . . . , dk ) with 1 ≤ a + jb + di ≤ N (i = 1, 2, . . . , k). In [18] the connection between the measures W and C2 was studied. Bull Braz Math Soc, Vol. 39, N. 3, 2008
“main” — 2008/8/27 — 17:44 — page 389 — #3
ON A PROBLEM OF D.H. LEHMER AND PSEUDORANDOM BINARY SEQUENCES
389
The sequence is considered as a “good” pseudorandom sequence if both W (E N ) and Ck (E N ) (at least for small k) are “small” in terms of N . J. Cassaigne, C. Mauduit and A. Sárközy [6] proved that this terminology is justified since for almost all E N ∈ {−1, +1} N , both W (E N ) and Ck (E N ) are less than 1 N 2 (log N )c . Later a few pseudorandom binary sequences were given and studied (see [4], [5], [8], [9], [11], [12], [13], [14], [16], [17], [19], [21]), and the properties of the pseudorandom measures were also researched in [2] and [3]. Define ( (−1)n+n+x , if p - n(n + x), n (1) , en = en(2) = (−1)n+n p 1, otherwise, and
(1) (1) (2) (2) (2) E (1) p−1 = e1 , . . . , e p−1 , E p−1 = e1 , . . . , e p−1 .
The first author proved that (1) 3 1/2 1/2 p p) E W E (1) , C (log (log p)5 , 2 p−1 p−1 p 1/2 Q 2 E (1) (log p)5 , p−1 p
(2) 2 1/2 1/2 p) p E W E (2) , C (log (log p)3 , 2 p−1 p−1 p 1/2 Q 2 E (2) (log p)3 , p−1 p
in [12] and [13] respectively. Moreover, suppose that f (x) ∈ F p [x] has degree (3) (3) (0 <)d(< p) and no multiple zero in F p . Let E (3) p−1 = e1 , . . . , e p−1 be defined by ( (−1) f (n)+ f (n+x) , if p - f (n) f (n + x), (3) en = 1, otherwise. Assume that k ∈ N such that k = 2 or (4d)k < p. The first author [14] showed that 1/2 (log p)3 , W (E (3) p−1 ) dp
1/2 Ck (E (3) (log p)2k+1 , p−1 ) kdp
1/2 Q k (E (3) (log p)2k+1 . p−1 ) kdp
Furthermore, let f (x) ∈ F p [x] of degree d with 1 ≤ d < p, and let s be its number of distinct roots in F p [x]. Define ( +1, if f (n) ≡ R p ( f (n))(mod 2), en = (1.2) −1, if f (n) 6≡ R p ( f (n))(mod 2), Bull Braz Math Soc, Vol. 39, N. 3, 2008
“main” — 2008/8/27 — 17:44 — page 390 — #4
390
HUANING LIU and CUNDIAN YANG
and E p = (e1 , . . . , e p ), where R p (x) denotes the unique r ∈ {0, 1, . . . , p − 1} with x ≡ r (mod p). S.R. Louboutin et al. [15] proved that W (E p ) (d + s) p 1/2 (log p)3 ,
C2 (E p ) (d + s) p 1/2 (log p)5 .
This shows that {en } is a “good” pseudorandom binary sequence. In this paper we shall give a generalization on (1.2) by using Lemma 5 of [19]. Following is the main theorem.
Theorem 1.1. Let p be an odd prime, f (x) ∈ F p [x] has degree (0 <)d(< p) and no multiple zero in F p . For any g(x) ∈ F p [x], define ( +1, if f (n) ≡ R p (g(n))(mod 2), 0 (1.3) en = −1, if f (n) 6≡ R p (g(n))(mod 2),
and E 0p = {e10 , . . . , e0p }. Assume that k ∈ N with 2 ≤ k ≤ p, and one of the following conditions holds: Then we have
k = 2;
(i) W E 0p
Ck E p
0
Q k E 0p
(ii)
(4d)k < p.
(d + deg g) p 1/2 (log p)3 ,
(kd + deg g) p 1/2 (log p)2k+1 , (kd + deg g) p 1/2 (log p)2k+1 .
There are some generalizations on the problem of D.H. Lehmer. Let q > 2 be an odd number, and q X 1. N (q) = W. Zhang [23] proved that
n=1 (n,q)=1 2-n+n
1 1 φ(q) + O q 2 d 2 (q) log2 q , 2 where φ(q) is the Euler function, and d(q) is the divisor function. For any nonnegative integer k, let N (q) =
N (q, k) =
Bull Braz Math Soc, Vol. 39, N. 3, 2008
q X
n=1 (n,q)=1 2-n+n
(n − n)2k .
“main” — 2008/8/27 — 17:44 — page 391 — #5
ON A PROBLEM OF D.H. LEHMER AND PSEUDORANDOM BINARY SEQUENCES
391
W. Zhang [24] gave a sharp asymptotic formula for N (q, k) as following: N (q, k) =
1 1 φ(q)q 2k + O 4k q 2k+ 2 d 2 (q) log2 q . (2k + 1)(2k + 2)
Moreover, for 0 ≤ x, y ≤ 1, he [24] proved that Fq (x, y) =
X
n≤xq,n≤yq (n,q)=1 2-n+n
1=
1 1 x yφ(q) + O q 2 d 2 (q) log2 q . 2
C. Cobeli and A. Zaharescu [7] gave a generalization on this problem. For details, let p be a prime, C be an irreducible curve of degree ≤ d in Ar F p , defined over F p and not contained in any hyperplane. Let a = (a1 , . . . , ar ), b = (b1 , . . . , br ) ∈ Zr with a1 , . . . , ar ≥ 1. We say that an x = (x1 , . . . , xr ) ∈ Zr , with 0 ≤ x1 , . . . , xr < p, is a Lehmer point with respect to p, r , C , a and b if x(mod p) ∈ C and x j ≡ b j (mod a j ), for 1 ≤ j ≤ r . We denote by L( p, r, C , a, b) the set of Lehmer points. For t = (t1 , . . . , tr ), 0 ≤ t1 , . . . , tr ≤ 1, let F( p, r, C , a, b; t) = # x = (x1 , . . . , xr ) ∈ L( p, r, C , a, b) : x j ≤ t j p, 1 ≤ j ≤ r .
C. Cobeli and A. Zaharescu showed that F( p, r, C , a, b; t) =
1 t1 ∙ ∙ ∙ tr p + Or,d p 2 logr p . a1 ∙ ∙ ∙ ar
Furthermore, let k ≥ 1, q ≥ 2 be integers and let a1 , . . . , ak+1 ≥ 2 and b1 , . . . , bk+1 ≥ 0 with 0 ≤ bi < ai , for all i ∈ {1, 2, . . . , k + 1}, be integers such that (q, a1 a2 ∙ ∙ ∙ ak+1 ) = 1. Denote N (a, b; q) =
q−1 X
∙∙∙
q−1 X
n 1 =1 n k =1 (n 1 ,q)=1 (n k ,q)=1 n 1 ≡b1 ( mod a1 ) n k ≡bk ( mod ak ) n 1 ∙∙∙n k ≡bk+1 ( mod ak+1 )
1.
E. Alkan, F. Stan and A. Zaharescu [1] showed that N (a, b; q) =
φ k (q) 1 + Ok, q k− 2 + . a1 a2 ∙ ∙ ∙ ak+1
Now we give a generalization on the problem of D.H. Lehmer, by using Theorem 1.1. We shall prove the following: Bull Braz Math Soc, Vol. 39, N. 3, 2008
“main” — 2008/8/27 — 17:44 — page 392 — #6
392
HUANING LIU and CUNDIAN YANG
Theorem 1.2. Define p, f (x), g(x), d and k in the same way as in Theorem 1.1. For any integers a, b, d1 , d2 , . . . , dk with 0 ≤ a < b, (b, p) = 1 and 0 ≤ d1 < d2 < ∙ ∙ ∙ < dk , define D = (d1 , d2 , . . . , dk ), and p X
N (a, b, D, k, f, g, p) =
n=1 n≡a( mod b) p - f (n+d1 )∙∙∙ f (n+dk )
1.
(1.4)
2- R p (g(n+d1 ))+ f (n+d1 ) ∙∙∙∙∙∙ 2- R p (g(n+dk ))+ f (n+dk )
Then we have
N (a, b, D, k, f, g, p) =
2 Some Lemmas
p + O (kd + deg g) p 1/2 (log p)2k+1 . k 2b
To prove the theorems, we need the following lemmas.
Lemma 2.1 ([20]). For any polynomials g(x), h(x) ∈ F p [x] such that the rational function f (x) = g(x)/ h(x) is not constant on F p , let s be the number of distinct roots of the polynomial h(x), then we have X g(n) √ e ≤ (max (deg g, deg h) + s − 1) p. h(n) p n∈F p h(n)6=0
Lemma 2.2. Define p, f (x), d and k in the same way as in Theorem 1.1. Then for any integers l, d1 , . . . , dl , s1 , . . . , sl with 1 ≤ l ≤ k, d1 < d2 < ∙ ∙ ∙ < dl and (s1 ∙ ∙ ∙ sl , p) = 1, the polynomial (n) := is not constant on F p .
l X i=1
si
l Y j=1 j6=i
f (n + d j )
Proof. This lemma can be easily deduced from Lemma 5 of [19]. Bull Braz Math Soc, Vol. 39, N. 3, 2008
¤
“main” — 2008/8/27 — 17:44 — page 393 — #7
ON A PROBLEM OF D.H. LEHMER AND PSEUDORANDOM BINARY SEQUENCES
393
Lemma 2.3. Define p, f (x), g(x), d and k in the same way as in Theorem 1.1. For any integers a, b, u, d1 , d2 , . . . , dk , r1 , . . . , rk , s1 , . . . , sk such that d1 < d2 < ∙ ∙ ∙ < dk and (br1 ∙ ∙ ∙ rk , p) = 1, we have 9
:=
p−1 X
j=0 p - f (a+ jb+d1 )∙∙∙ f (a+ jb+dk )
s1 g(a + jb + d1 ) + ∙ ∙ ∙ + sk g(a + jb + dk ) + u j p √ (kd + deg g) p. ×e
Proof.
r1 f (a + jb + d1 ) + ∙ ∙ ∙ + rk f (a + jb + dk ) e p
!
From the properties of residue systems we have 9 =
Define R( j) =
p−1 X
j=0 p - f ( j+d1 )∙∙∙ f ( j+dk )
r1 f ( j + d1 ) + ∙ ∙ ∙ + rk f ( j + dk ) e p
!
! s1 g( j + d1 ) + ∙ ∙ ∙ + sk g( j + dk ) + ub( j − a) . ×e p Qk
t=1
f ( j + dt ), and Q( j) =
k X i=1
ri
k Y t=1 t6=i
f ( j + dt )
+ s1 g( j + d1 ) + ∙ ∙ ∙ + sk g( j + dk ) + ub( j − a) Therefore 9=
X
j∈F p R( j)6 =0
e
Q( j) . R( j) p
k Y t=1
f ( j + dt ).
If p - s1 g( j + d1 ) + ∙ ∙ ∙ + sk g( j + dk ) + ub( j − a), then 0 < deg R < deg Q and the rational function Q/R over F p is not constant. Then from Lemma 2.1 √ we have 9 (kd + deg g) p. Bull Braz Math Soc, Vol. 39, N. 3, 2008
“main” — 2008/8/27 — 17:44 — page 394 — #8
394
HUANING LIU and CUNDIAN YANG
If p | s1 g( j + d1 ) + ∙ ∙ ∙ + sk g( j + dk ) + ub( j − a), by Lemma 2.2 we know √ that Q( j) can not be constant on F p . Then from Lemma 2.1 we get 9 kd p. √ ¤ Therefore 9 (kd + deg g) p. 3 Proof of the theorems
First we prove Theorem 1.1. For 1 ≤ a + tb + di ≤ p, i = 1, 2, . . . , k, 0 ≤ d1 < d2 < ∙ ∙ ∙ < dk , by (1.3) and the trigonometric identity ( p X p, if p | n, un e = (3.1) p 0, if p - n. u=1 we have t X
j=0
=
=
0 0 ea+ jb+d1 ∙ ∙ ∙ ea+ jb+dk
j=0 p - f (a+ jb+d1 ) ∙∙∙ f (a+ jb+dk )
1
p 2k+1
×
×
=
t X
p p X X
n k =1 sk =1
p−1 X
rk =1
! p−1 p p t X X r1 f (a + jb + d1 ) − m 1 u( j − l) X X e e p p
j=0 l=0 u=1 p - f (a+ jb+d1 ) ∙∙∙ f (a+ jb+dk )
n 1 =1 s1 =1
p 2k+1
×
p−1 X
p X p X
1
(−1) f (a+ jb+d1 )+R p (g(a+ jb+d1 ))+∙∙∙+ f (a+ jb+dk )+R p (g(a+ jb+dk )) + O(kd)
p−1 X
r1 =1
m 1 =1 r1 =1
p−1 p X X
s1 g(a + jb + d1 ) − n 1 e p
!
∙∙∙
e
sk g(a + jb + dk ) − n k p
!
(−1)m 1 +n 1 +∙∙∙+m k +n k + O(kd)
p−1 X
p−1 X
m 1 =1
X p p X s n 1 1 n ∙∙∙ (−1) 1 e − p p
m r (−1)m 1 e − 1 1
m k =1
s1 =1
n 1 =1
!
X X p p p t X X s n ul k k n (−1) k e − e − p p p
m k rk (−1)m k e −
m k =1 rk =1
rk f (a + jb + dk ) − m k e p
Bull Braz Math Soc, Vol. 39, N. 3, 2008
sk =1
n k =1
u=1
l=0
“main” — 2008/8/27 — 17:44 — page 395 — #9
ON A PROBLEM OF D.H. LEHMER AND PSEUDORANDOM BINARY SEQUENCES p−1 X
×
j=0 p - f (a+ jb+d1 ) ∙∙∙ f (a+ jb+dk )
395
! r1 f a + jb + d1 + ∙ ∙ ∙ + rk f a + jb + dk e p
! s1 g a + jb + d1 + ∙ ∙ ∙ + sk g a + jb + dk + u j + O(kd). ×e p
Since
t X ul 1 e − , for p - u; p sin πpu l=0 p−1 X mr 1 m , (−1) e − p sin π2 − πrp m=1
from Lemma 2.3 we have t X
0 0 ea+ jb+d ∙ ∙ ∙ ea+ jb+d
p 2k+1
j=0
k
1
+
t
1
p 2k+1
p−1 X
1
k
p X
1
k
√ (kd + deg g) p π − πr π − πs sin sin r =1 s=1 p p 2 2
k p p−1 X X 1 1 √ (kd + deg g) p π − πr π − πs πu r =1 sin 2 s=1 sin 2 u=1 sin p p p p−1 X
1
k
(kd + deg g) p 1/2 (log p)2k+1 .
Therefore
Qk
X t 0 0 0 ea+ jb+d1 ∙ ∙ ∙ ea+ jb+dk E p = max a,b,t,D j=0 (kd + deg g) p 1/2 (log p)2k+1 .
Taking k = 1 and d1 = 0 in (3.2), we get X t−1 0 0 ea+ jb (d + deg g) p 1/2 (log p)3 . W E p = max a,b,t j=0
Bull Braz Math Soc, Vol. 39, N. 3, 2008
(3.2)
“main” — 2008/8/27 — 17:44 — page 396 — #10
396
HUANING LIU and CUNDIAN YANG
And taking a = 0, b = 1, j = n − 1 and t = M − 1 in (3.2), we immediately have M X 0 0 1/2 Ck E 0p = max en+d ∙ ∙ ∙ e (log p)2k+1 . n+dk (kd + deg g) p 1 M,D n=1
This proves Theorem 1.1. Now we prove Theorem 1.2. By (1.4) we get p X
N (a, b, D, k, f, g, p) =
1 = k 2
1 = k 2
×
n=1 n≡a( mod b) p - f (n+d1 )∙∙∙ f (n+dk )
2- R p (g(n+d1 ))+ f (n+d1 ) ∙∙∙∙∙∙ 2- R p (g(n+dk ))+ f (n+dk )
p X
1 − (−1) R p (g(n+d1 ))+ f (n+d1 ) ∙ ∙ ∙ 1 − (−1) R p (g(n+dk ))+ f (n+dk )
n=1 n≡a( mod b) p - f (n+d1 )∙∙∙ f (n+dk ) p X
n=1 n≡a( mod b) p - f (n+d1 )∙∙∙ f (n+dk ) p X
n=1 n≡a( mod b) p - f (n+d1 )∙∙∙ f (n+dk )
k 1 X 1+ k (−1)l 2 l=1
1 2k
p X
1≤i 1 <∙∙∙
n=1 n≡a( mod b) p - f (n+d1 )∙∙∙ f (n+dk )
On the other hand, by (3.2) we have n=1 n≡a( mod b) p - f (n+d1 )∙∙∙ f (n+dk )
X
(−1) R p (g(n+di1 ))+ f (n+di1 )+∙∙∙+R p (g(n+dil ))+ f (n+dil ) .
It is easy to show that
p X
1
1=
p + O(d). 2k b
(−1) R p (g(n+di1 ))+ f (n+di1 )+∙∙∙+R p (g(n+dil ))+ f (n+dil )
Bull Braz Math Soc, Vol. 39, N. 3, 2008
“main” — 2008/8/27 — 17:44 — page 397 — #11
ON A PROBLEM OF D.H. LEHMER AND PSEUDORANDOM BINARY SEQUENCES
=
=
397
(−1) R p (g(n+di1 ))+ f (n+di1 )+∙∙∙+R p (g(n+dil ))+ f (n+dil ) + O(kd)
X
0≤ j≤( p−a)/b p - f (a+ jb+di1 )∙∙∙ f (a+ jb+dil )
X
0≤ j≤( p−a)/b
0 0 ea+ jb+di ∙ ∙ ∙ ea+ jb+di + O(kd) 1
l
(kd + deg g) p 1/2 (log p)2k+1 .
Therefore
N (a, b, D, k, f, g, p) =
p + O (kd + deg g) p 1/2 (log p)2k+1 . k 2b
This completes the proof of Theorem 1.2. Acknowledgments. helpful comments.
The authors express their gratitude to the referee for his
References
[1]
[2] [3] [4] [5] [6] [7] [8]
E. Alkan, F. Stan and A. Zaharescu. Lehmer k-tuples. Proceedings of the American Mathematical Society, 134 (2006), 2807–2815. N. Alon, Y. Kohayakawa, C. Mauduit, C.G. Moreira and V. Rödl. Measures of pseudorandomness for finite sequences: minimal values. Combinatorics, Probability and Computing, 15 (2006), 1–29.
N. Alon, Y. Kohayakawa, C. Mauduit, C.G. Moreira and V. Rödl. Measures of pseudorandomness for finite sequences: typical values. Proceedings of the London Mathematical Society, 95 (2007), 778–812.
J. Cassaigne, S. Ferenczi, C. Mauduit, J. Rivat and A. Sárközy. On finite pseudorandom binary sequences III: the Liouville function. I. Acta Arithmetica, 87 (1999), 367–390. J. Cassaigne, S. Ferenczi, C. Mauduit, J. Rivat and A. Sárközy. On finite pseudorandom binary sequencs IV: the Liouville function. II. Acta Arithmetica, 95 (2000), 343–359. J. Cassaigne, C. Mauduit and A. Sárközy. On finite pseudorandom binary sequences VII: the measures of pseudorandomness. Acta Arithmetica, 103 (2002), 97–108. C. Cobeli and A. Zaharescu. Generalization of a problem of Lehmer. Manuscripta Mathematica, 104 (2001), 301–307. E. Fouvry, P. Michel, J. Rivat and A. Sárközy. On the pseudorandomness of the signs of Kloosterman sums. Journal of the Australian Mathematical Society, 77 (2004), 425–436.
Bull Braz Math Soc, Vol. 39, N. 3, 2008
“main” — 2008/8/27 — 17:44 — page 398 — #12
398
HUANING LIU and CUNDIAN YANG
[9]
L. Goubin, C. Mauduit and A. Sárközy. Construction of large families of pseudorandom binary sequences. Journal of Number Theory, 106 (2004), 56–69. R.K. Guy. Unsolved problems in number theory. Springer-Verlag, New York, (1981), 139–140. K. Gyarmati. On a family of pseudorandom binary sequences. Periodica Mathematica Hungarica, 49 (2004), 45–63. H. Liu. New pseudorandom sequences constructed by multiplicative inverse. Acta Arithmetica, 125 (2006), 11–19. H. Liu. New pseudorandom sequences constructed by quadratic residues and Lehmer numbers. Proceedings of the American Mathematical Society, 135 (2007), 1309–1318. H. Liu. A family of pseudorandom binary sequences constructed by the multiplicative inverse. Acta Arithmetica,130 (2007), 167–180.
[10] [11] [12] [13] [14]
[15] S.R. Louboutin, J. Rivat and A. Sárközy. On a problem of D.H. Lehmer. Proceedings of the American Mathematical Society, 135 (2007), 969–975. [16] C. Mauduit, J. Rivat and A. Sárközy. Construction of pseudorandom binary sequences using additive characters. Monatshefte für Mathematik, 141 (2004), 197–208. [17] C. Mauduit and A. Sárközy. On finite pseudorandom binary sequences I: measure of pseudorandomness, the Legendre symbol. Acta Arithmetica, 82 (1997), 365–377.
[18] C. Mauduit and A. Sárközy. On the measures of pseudorandomness of binary sequences. Discrete Mathematics, 271 (2003), 195–207. [19] C. Mauduit and A. Sárközy. Construction of pseudorandom binary sequences by using the multiplicative inverse. Acta Mathematica Hungarica, 108 (2005), 239–252. [20] C.J. Moreno and O. Moreno. Exponential sums and Goppa codes: I. Proceedings of the American Mathematical Society, 111 (1991), 523–531. [21] A. Sárközy. A finite pseudorandom binary sequence. Studia Scientiarum Mathematicarum Hungarica, 38 (2001), 377–384. [22] W. Zhang. A problem of D.H. Lehmer and its Generalization (I). Compositio Mathematica, 86 (1993), 307–316.
[23] W. Zhang. A problem of D.H. Lehmer and its Generalization (II). Compositio Mathematica, 91 (1994), 47–56. [24] W. Zhang. On the difference between a D.H. Lehmer number and its inverse modulo q. Acta Arithmetica, 68 (1994), 255–263.
Bull Braz Math Soc, Vol. 39, N. 3, 2008
“main” — 2008/8/27 — 17:44 — page 399 — #13
ON A PROBLEM OF D.H. LEHMER AND PSEUDORANDOM BINARY SEQUENCES
Huaning Liu Department of Mathematics Northwest University Xi’an, Shaanxi P.R. CHINA
E-mail:
[email protected] Cundian Yang Department of Mathematics Shangluo University Shangluo, Shaanxi P.R. CHINA E-mail:
[email protected]
Bull Braz Math Soc, Vol. 39, N. 3, 2008
399
