The 2-adic complexity has been well-analyzed in the periodic case. However, we are not aware of any theoretical results in the aperiodic case. In particular, theNth 2-adic complexity has not been studied for any promising candidate of a pseudorandom sequence of finite lengthN. Also nothing seems be known for a part of the period of lengthNof any cryptographically interesting periodic sequence. Here we introduce the first method for this aperiodic case. More precisely, we study the relation betweenNth maximum-order complexity andNth 2-adic complexity of binary sequences and prove a lower bound on theNth 2-adic complexity in terms of theNth maximum-order complexity. Then any known lower bound on theNth maximum-order complexity implies a lower bound on theNth 2-adic complexity of the same order of magnitude. In the periodic case, one can prove a slightly better result. The latter bound is sharp, which is illustrated by the maximum-order complexity of ℓ-sequences. The idea of the proof helps us to characterize the maximum-order complexity of periodic sequences in terms of the unique rational number defined by the sequence. We also show that a periodic sequence of maximal maximum-order complexity must be also of maximal 2-adic complexity.

In the most interesting case of safe prime powers q, Gómez and Winterhof showed that a subfamily of the family of Golomb Costas permutations of$\{1,2,\ldots,q-2\}$of size$\varphi (q-1)$has maximal cross-correlation of order of magnitude at most$q^{1/2}$. In this paper we study a larger family of Golomb Costas permutations and prove a weaker bound on its maximal cross-correlation. Considering the whole family of Golomb Costas permutations we show that large cross-correlations are very rare. Finally, we collect several conditions for a small cross-correlation of two Costas permutations. Our main tools are the Weil bound and the Szemerédi-Trotter theorem for finite fields.

The (classical) crosscorrelation is an important measure of pseudorandomness of two binary sequences for applications in communications. The arithmetic crosscorrelation is another figure of merit introduced by Goresky and Klapper generalizing Mandelbaum’s arithmetic autocorrelation. First we observe that the arithmetic crosscorrelation is constant for two binary sequences of coprime periods, which complements the analogous result for the classical crosscorrelation. Then we prove upper bounds for the constant arithmetic crosscorrelation of two Legendre sequences of different periods and of two binary$m$-sequences of coprime periods, respectively.

Let 11φ(p-1)n) defined by sn≡ gn+1+gn+2mod 2, n=0,1,⋯ In particular, we study the balance, linear complexity and 2-adic complexity of (sn). We show that for a typical p the sequence (sn) is quite unbalanced. However, there are still infinitely many p such that (sn) is very balanced. We also prove similar results for the distribution of longer patterns. Moreover, we give general lower bounds on the linear complexity and 2-adic complexity of (sn) and state sufficient conditions for attaining their maximums. Hence, for carefully chosen p, these sequences are attractive candidates for cryptographic applications.

We study subsets of the $n$-dimensional vector space over the finite field $\mathbb{F}_q$, 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\ge 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 $q^n$ if we take lower-dimensional objects, such as circles in $\mathbb{F}_q^3$ 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 $\mathbb{F}_q$.

It is known that Hall's sextic residue sequence has some desirable features of pseudorandomness: an ideal two-level autocorrelation and linear complexity of the order of magnitude of its period p. Here we study its correlation measure of order k and show that it is, up to a constant depending on k and some logarithmic factor, of order of magnitude p1/2, which is close to the expected value for a random sequence of length p. Moreover, we derive from this bound a lower bound on the Nth maximum order complexity of order of magnitude log p, which is the expected order of magnitude for a random sequence of length p.

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/2otherwise. 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/2otherwise. Note that we consider a smaller family than Drakakis et al. Our family is of size φ(q - 1) whereas there are φ(q - 1)2different 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.

Hu introduced a simple method to compute the 2-adic complexity of any periodic binary sequence with ideal two-level autocorrelation. We extend this approach to some other sequences. First, we provide a substantially shorter proof of the maximality of the 2-adic complexity of the Legendre sequence of period N ≡ 1 mod 4 first proved by Xiong et al. Then, we show that the 2-adic complexity of the two-prime generator of period pq with two odd primes p≠q attains the maximum if (q + 1)/4 ≤ p ≤ 4q - 1. This result was only known for twin primes q = p+2 before. For arbitrary odd primes p ≠ q, we can still prove that the 2-adic complexity of the two-prime generator is close to its period.

For a given polynomial $P(X)$ of degree $d\ge 1$ modulo $p$, we estimate the number of elements $1\le u

For a set M = {-μ, -μ + 1, ... , λ} \ {0} with nonnegative integers λ, μqmodulo an integer q > 1 is called a (λ, μ; q)-covering set if MS = {ms mod q : m ∈ M, s ∈ S} = Zq. Small covering sets play an important role in codes correcting limited-magnitude errors. We give an explicit construction of a (λ, μ; q)-covering set S, which is of the size q1+o(1)max{λ, μ}-1/2for almost all integers q ≥ 1 and optimal order of magnitude (that is up to a multiplicative constant) p max{λ, μ}-1if q = p is prime. Furthermore, using a bound on the fourth moment of character sums of Cochrane and Shi that there is a (λ, μ; q)-covering set of size at most q1+o(1)max{λ, μ}-1/2for any integer q ≥ 1, however the proof of this bound is not constructive.

We combine the concepts of thep-periodic Legendre sequence, the(q-1)-periodic Sidelnikov sequence and the two-prime generator to introduce a newp(q-1)-periodic sequence called Legendre-Sidelnikov sequence. We show that this new sequence is balanced ifp=q. For an arbitrary odd primepand an arbitrary powerqof an odd prime withgcd (p,q-1)=1 we determine the exact values of its (periodic) autocorrelation function and deduce an upper bound on its aperiodic autocorrelation function showing that it is small compared to its period.

For a Sidelnikov sequence of period p/sup m/-1, tight lower bounds are obtained on its linear complexity L over F/sub p/. In particular, these bounds imply that, uniformly over all p and m, L is close to its largest possible value p/sup m/-1.

The two-prime generator of order 2 has several desirable randomness properties if the two primes are chosen properly. In particular, Ding deduced exact formulas for the (periodic) autocorrelation and the linear complexity of these sequences. In this note, we analyze parts of the period of the two-prime generator of order 2 and obtain bounds on the aperiodic autocorrelation and linear complexity profile.

We obtain lower bounds on the linear and nonlinear complexity profile of a general nonlinear pseudorandom number generator, of the inversive generator, and of a new nonlinear generator called quadratic exponential generator. The results are interesting for applications to cryptography and Monte Carlo methods.

We show that for several natural classes of “structured” matrices, including symmetric, circulant, Hankel and Toeplitz matrices, approximating the permanent modulo a prime p is as hard as computing its exact value. Results of this kind are well known for arbitrary matrices. However the techniques used do not seem to apply to “structured” matrices. Our approach is based on recent advances in the hidden number problem introduced by Boneh and Venkatesan in 1996 combined with some bounds of exponential sums motivated by the Waring problem in finite fields.

Let p be a prime, r a positive integer, q=p/sup r/, and d a divisor of p(q-1). We derive lower bounds on the linear complexity over the residue class ring Z/sub d/ of a (q-periodic) sequence representing the residues modulo d of the discrete logarithm in F/sub q/. Moreover, we investigate a sequence over F/sub q/ representing the values of a certain polynomial over F/sub q/ introduced by Mullen and White (1986) which can be identified with the discrete logarithm in F/sub q/ via p-adic expansions and representations of the elements of F/sub q/ with respect to some fixed basis.