Paper 2026/829

Beyond Binary: crosscorrelation of Cubic, Quartic and Quintic Character Sequences

Abstract

The arithmetic crosscorrelation of pseudorandom sequences is a key measure of their suitability for cryptographic and communication applications. While prior work has addressed this quantity for binary sequences, the non-binary setting has remained largely unexplored. This paper initiates a systematic study of the arithmetic crosscorrelation of non-binary pseudorandom sequences constructed from higher-order multiplicative characters over finite fields. For two sequences of coprime periods $P$ and $Q$, defined via $r$-th order characters of polynomials of degree $d$, we show that the joint local patterns of the sequences are asymptotically uniformly distributed, and use this to derive an explicit bound on the arithmetic crosscorrelation $C^A_{S,T}(\tau)$. Specifically, we establish $$ \mathcal{N}\big(C^A_{S,T}(\tau)\big) \ = \ O\Big(\big(\varphi(r)d P^{1/2} Q (\log P)^2\big)^{\varphi(r)}\Big) $$ for all shifts $\tau$, for $r$-th order character sequences, where $\varphi(\cdot)$ is the Euler totient function and $\mathcal{N}(\cdot)$ denotes the norm function. To the best of our knowledge, this work establishes the first nontrivial upper bounds on the arithmetic crosscorrelation of non-binary pseudorandom sequences, thereby extending the results of Chen et al. [IEEE IT'22] and Yan and Ke [ePrint: 2026/616], which were obtained exclusively for the Legendre sequence.