On the pseudorandom properties of subsets constructed by using primitive roots
- PDF / 365,303 Bytes
- 21 Pages / 439.37 x 666.142 pts Page_size
- 42 Downloads / 171 Views
On the pseudorandom properties of subsets constructed by using primitive roots Huaning Liu1
· Mengyao Jing1
Received: 16 January 2020 / Accepted: 31 July 2020 © Springer Science+Business Media, LLC, part of Springer Nature 2020
Abstract Dartyge and Sárközy (partly with other coauthors) introduced pseudorandom measures of subsets, and studied the pseudorandomness of certain subsets related to primitive roots. In this paper we answer a conjecture of Dartyge, Sárközy and Szalay, and study the pseudorandom properties of some subsets constructed by using primitive roots. Keywords Primitive root · Pseudorandom subset · Character sum Mathematics Subject Classification 11K45 · 11K38 · 11A07 · 11L40
1 Introduction The need for pseudorandom subsets arises in many cryptographic applications, so numerous papers have been written on this subject. In these papers a wide range of goals, approaches, tools is presented, even the concept of “pseudorandomness” is interpreted in different ways. Let R ⊂ {1, 2, . . . , N } and define the sequence |R| N |R| , − E N = E N (R) = {e1 , e2 , . . . , e N } ∈ 1 − N N
This work is supported by the National Natural Science Foundation of China under Grant No. 11571277, and the Science and Technology Program of Shaanxi Province of China under Grant No. 2019JM-573 and 2020JM-026.
B
Huaning Liu [email protected] Mengyao Jing [email protected]
1
School of Mathematics, Northwest University, Xi’an 710127, Shaanxi, People’s Republic of China
123
H. Liu, M. Jing
by en =
| 1 − |R N for n ∈ R, | − |R N
for n ∈ / R.
Dartyge and Sárközy [3] introduced the measures of pseudorandomness: The welldistribution measure of the subset R is defined by t−1 ea+ jb , W (R, N ) = max 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 the subset R is defined by M Ck (R, N ) = max en+l1 . . . en+lk , M,L n=1
where the maximum is taken over all L = (l1 , . . . , lk ) and M with 0 ≤ l1 < · · · < lk ≤ N − M. The subset R is considered to be a pseudorandom subset if both W (R, N ) and Ck (R, N ) (at least for small k) are “small” in terms of N . Later many pseudorandom subsets were constructed and studied (see [2–6,8]). Let p > 2 be a prime and let G p be the set of the primitive roots modulo p. Many papers have been written on the distribution of the primitive roots modulo p. For example, let f (x) be a polynomial over F p such that f (x) is not of the form cg(x)k for k > 1 and k | p − 1, and let N ( f ) be the number of x’s in F p such that f (x) ∈ G p . Carlitz [1] proved that 1 N ( f ) = φ( p − 1) + O φ( p − 1)2ω( p−1) p − 2 , where φ is the Euler function and ω(n) denotes the number of distinct prime factors of n. Let A, B be two subsets of F p and f (x, y) be a polynomial over F p with two variables. Let NA,B ( f ) denote the number of pairs (x, y) ∈ A×B such that f (x, y) ∈ G p . Suppose that the degrees of f (x, y) in variables x, y are n, m, respectively, and the pr
Data Loading...
