BZPEERSource author record
Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.
Catalog footprint
Published work
Let q=pr be the power of a prime p and (β1,…,βr) be an ordered basis of Fq over Fp. For $$ ξ=\sum\limits_{j=1}^r x_jβ_j\in \mathbb{F}_q \quad \mbox{with digits }x_j\in\mathbb{F}_p, $$ we define the Rudin-Shapiro function R on Fq by R(ξ)=i=1∑r−1xixi+1,ξ∈Fq. For a non-constant polynomial f(X)∈Fq[X] and c∈Fp we study the number of solutions ξ∈Fq of R(f(ξ))=c. If the degree d of f(X) is fixed, r≥6 and p→∞, the number of solutions is asymptotically pr−1 for any c. The proof is based on the Hooley-Katz Theorem.
We build on the work of Drakakis et al. (2011) on the maximal cross-correlation of the families of Welch and Golomb Costas permutations. In particular, we settle some of their conjectures. More precisely, we prove two results. First, for a prime p≥5, the maximal cross-correlation of the family of the φ(p−1) different Welch Costas permutations of {1,…,p−1} is (p−1)/t, where t is the smallest prime divisor of (p−1)/2 if p is not a safe prime and at most 1+p1/2 otherwise. Here φ denotes Euler's totient function and a prime p is a safe prime if (p−1)/2 is also prime. Second, for a prime power q≥4 the maximal cross-correlation of a subfamily of Golomb Costas permutations of {1,…,q−2} is (q−1)/t−1 if t is the smallest prime divisor of (q−1)/2 if q is odd and of q−1 if q is even provided that (q−1)/2 and q−1 are not prime, and at most 1+q1/2 otherwise. Note that we consider a smaller family than Drakakis et al. Our family is of size φ(q−1) whereas there are φ(q−1)2 different Golomb Costas permutations. The maximal cross-correlation of the larger family given in the tables of Drakakis et al. is larger than our bound (for the smaller family) for some q.
For a prime p≥5 let q0,q1,…,q(p−3)/2 be the quadratic residues modulo p in increasing order. We study two (p−3)/2-periodic binary sequences (dn) and (tn) defined by dn=qn+qn+1mod2 and tn=1 if qn+1=qn+1 and tn=0 otherwise, n=0,1,…,(p−5)/2. For both sequences we find some sufficient conditions for attaining the maximal linear complexity (p−3)/2. Studying the linear complexity of (dn) was motivated by heuristics of Caragiu et al. However, (dn) is not balanced and we show that a period of (dn) contains about 1/3 zeros and 2/3 ones if p is sufficiently large. In contrast, (tn) is not only essentially balanced but also all longer patterns of length s appear essentially equally often in the vector sequence (tn,tn+1,…,tn+s−1), n=0,1,…,(p−5)/2, for any fixed s and sufficiently large p.
We study subsets of the n-dimensional vector space over the finite field Fq, for odd q, which contain either a sphere for each radius or a sphere for each first coordinate of the center. We call such sets radii spherical Kakeya sets and center spherical Kakeya sets, respectively. For n≥4 we prove a general lower bound on the size of any set containing q−1 different spheres which applies to both kinds of spherical Kakeya sets. We provide constructions which meet the main terms of this lower bound. We also give a construction showing that we cannot get a lower bound of order of magnitude~qn if we take lower dimensional objects such as circles in Fq3 instead of spheres, showing that there are significant differences to the line Kakeya problem. Finally, we study the case of dimension n=1 which is different and equivalent to the study of sum and difference sets that cover Fq.
Carlitz rank and index are two important measures for the complexity of a permutation polynomial f(x) over the finite field $\F_q$. In particular, for cryptographic applications we need both, a high Carlitz rank and a high index. In this article we study the relationship between Carlitz rank Crk(f) and index Ind(f). More precisely, if the permutation polynomial is neither close to a polynomial of the form ax nor a rational function of the form ax−1, then we show that Crk(f)>q−max{3Ind(f),(3q)1/2}. Moreover we show that the permutation polynomial which represents the discrete logarithm guarantees both a large index and a large Carlitz rank.
The well-known Chowla and Zassenhaus conjecture, proven by Cohen in 1990, states that for any d≥2 and any prime p>(d2−3d+4)2 there is no complete mapping polynomial in Fp[x] of degree d. For arbitrary finite fields Fq, we give a similar result in terms of the Carlitz rank of a permutation polynomial rather than its degree. We prove that if n<⌊q/2⌋, then there is no complete mapping in Fq[x] of Carlitz rank n of small linearity. We also determine how far permutation polynomials f of Carlitz rank n<⌊q/2⌋ are from being complete, by studying value sets of f+x. We provide examples of complete mappings if n=⌊q/2⌋, which shows that the above bound cannot be improved in general.
The linear complexity is a measure for the unpredictability of a sequence over a finite field and thus for its suitability in cryptography. In 2012, Diem introduced a new figure of merit for cryptographic sequences called expansion complexity. We study the relationship between linear complexity and expansion complexity. In particular, we show that for purely periodic sequences both figures of merit provide essentially the same quality test for a sufficiently long part of the sequence. However, if we study shorter parts of the period or nonperiodic sequences, then we can show, roughly speaking, that the expansion complexity provides a stronger test. We demonstrate this by analyzing a sequence of binomial coefficients modulo p. Finally, we establish a probabilistic result on the behavior of the expansion complexity of random sequences over a finite field.
We study high-dimensional numerical integration in the worst-case setting. The subject of tractability is concerned with the dependence of the worst-case integration error on the dimension. Roughly speaking, an integration problem is tractable if the worst-case error does not explode exponentially with the dimension. Many classical problems are known to be intractable. However, sometimes tractability can be shown. Often such proofs are based on randomly selected integration nodes. Of course, in applications true random numbers are not available and hence one mimics them with pseudorandom number generators. This motivates us to propose the use of pseudorandom vectors as underlying integration nodes in order to achieve tractability. In particular, we consider digital inverse vectors and present two examples of problems, the weighted star discrepancy and integration of Hölder continuous, absolute convergent Fourier- and cosine series, where the proposed method is successful.
For a given elliptic curve E over a finite field of odd characteristic and a rational function f on E we first study the linear complexity profiles of the sequences f(nG), n=1,2,… which complements earlier results of Hess and Shparlinski. We use Edwards coordinates to be able to deal with many f where Hess and Shparlinski's result does not apply. Moreover, we study the linear complexities of the (generalized) elliptic curve power generators f(enG), n=1,2,…. We present large families of functions f such that the linear complexity profiles of these sequences are large.
We study the relationship between two measures of pseudorandomness for families of binary sequences: family complexity and cross-correlation measure introduced by Ahlswede et al.\ in 2003 and recently by Gyarmati et al., respectively. More precisely, we estimate the family complexity of a family (ei,1,…,ei,N)∈{−1,+1}N, i=1,…,F, of binary sequences of length N in terms of the cross-correlation measure of its dual family (e1,n,…,eF,n)∈{−1,+1}F, n=1,…,N. We apply this result to the family of sequences of Legendre symbols with irreducible quadratic polynomials modulo p with middle coefficient 0, that is, ei,n=(pn2−bi2)n=1(p−1)/2 for i=1,…,(p−1)/2, where b is a quadratic nonresidue modulo p, showing that this family as well as its dual family have both a large family complexity and a small cross-correlation measure up to a rather large order.
In this paper we study the non-existence problem of (nearly) perfect (almost) m-ary sequences via their connection to (near) Butson-Hadamard (BH) matrices and (near) conference matrices. Firstly, we apply a result on vanishing sums of roots of unity and a result of Brock on the unsolvability of certain equations over a cyclotomic number field to derive non-existence results for near BH matrices and near conference matrices. Secondly, we refine the idea of Brock in the case of cyclotomic number fields whose ring of integers is not a principal ideal domains and get many new non-existence results.
For an odd prime p and an integer w≥1, polynomial quotients qp,w(u) are defined by qp,w(u)≡puw−uwpmodp with 0≤qp,w(u)≤p−1, u≥0, which are generalizations of Fermat quotients qp,p−1(u). First, we estimate the number of elements 1≤u<N≤p for which f(u)≡qp,w(u)modp for a given polynomial f(x) over the finite field Fp. In particular, for the case f(x)=x we get bounds on the number of fixed points of polynomial quotients. Second, before we study the problem of estimating the smallest number (called the Waring number) of summands needed to express each element of Fp as sum of values of polynomial quotients, we prove some lower bounds on the size of their value sets, and then we apply these lower bounds to prove some bounds on the Waring number using results from bounds on additive character sums and additive number theory.
In this paper we give a short biography of Harald Niederreiter and we spotlight some cornerstones from his wide-ranging work. We focus on his results on uniform distribution, algebraic curves, polynomials and quasi-Monte Carlo methods. In the flavor of Harald's work we also mention some applications including numerical integration, coding theory and cryptography.
For a set $\cM=\{-μ,-μ+1,\ldots, λ\}\setminus\{0\}$ with non-negative integers λ,μ<q not both 0, a subset $\cS$ of the residue class ring Zq modulo an integer q≥1 is called a (λ,μ;q)-\emph{covering set} if $$ \cM \cS=\{ms \bmod q : m\in \cM,\ s\in \cS\}=\Z_q. $$ Small covering sets play an important role in codes correcting limited-magnitude errors. We give an explicit construction of a (λ,μ;q)-covering set $\cS$ which is of the size q1+o(1)max{λ,μ}−1/2 for almost all integers q≥1 and of optimal size pmax{λ,μ}−1 if q=p is prime. Furthermore, using a bound on the fourth moment of character sums of Cochrane and Shi we prove the bound ωλ,μ(q)≤q1+o(1)max{λ,μ}−1/2, for any integer q≥1, however the proof of this bound is not constructive.
We give a lower bound for the number of ordinary lines spanned by a modular hyperbola when the modulus is a prime power. We also give a partial answer to a question of Shparlinski.
Research graph
Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.
BZPEER is loading the nearby papers, people, topics and institutions for this page.