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.

Abstract The arithmetic correlations of two binary half‐ ℓ ‐sequences with connection integer p r , which is an odd prime power, are investigated. Possible values (of the arithmetic correlation) are calculated. In particular, if p ≡ 1 (mod 8), the authors prove that they are zero for non‐trivial shifts, that is, the half‐ ℓ ‐sequences have ideal arithmetic correlations. If p ≡ −1 (mod 8), an upper bound, which is of order of magnitude p r −1/2 ln p , is derived by using earlier results on the imbalance of half‐ ℓ ‐sequences with connection integer p studied by Gu and Klapper and later improved by Wang and Tan.

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 p be an odd prime and be a positive integer. The authorscontinue to investigate the binary sequence over defined from polynomial quotients by modulo p . The is generated in terms of which equals to the Legendre symbol of for u ≥ 0. In an earlier work, the linear complexity of was determined for (i.e. the case of Fermat quotients) under the assumption of . In this work, they develop a naive trick to calculate all possible values on the linear complexity of for all under the same assumption. They also state that the case of larger can be reduced to that of . So far, the linear complexity is almost determined for all kinds of Legendre‐polynomial quotients.

We continue the study of the properties of Boolean functions as reflected in The properties of a recently defined transform. For each non-constant Boolean function q, the q-transform of a Boolean function f is related to the Hamming distances from f to the functions obtainable from q by nonsingular linear change of basis. Many properties that can be characterized by the Walsh-Hadamard transform have (for each q) analogues that can be characterized by the q-transform. In this paper, we study one such property, bentness. We show that if q is balanced and not affine, then there is no function that is both bent and q-bent.

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.

This paper extends the concept of partially blind signature to the convertible undeniable partially blind signature, in which only the signer can verify and confirm the validity of given signatures and convert given signatures into universally verifiable signatures, along with a formal definition for it and a practical scheme that implements it. The proposed scheme is efficient and secure, in which its unforgeability is the same as that of the Schnorr's signature scheme and its untransferability relies on the hardness of decision Diffie-Hellman problem.