Using elliptic curves to construct 3D arrays (Q6962820)

For an alphabet \(A\) with \(k\) symbols, the Hamming distance in \(A^n\) counts the number of discrepancies among the letters of two \(n\)-words, and for any two such word \(m\)-sets their Hamming cross correlation is the \(m\)-array whose entries are additions, over index rotations of the second set, of the Hamming distance of each word in the first set to each word in the second set. The autocorrelation of a word set is its Hamming correlation with itself. A lower bound for the autocorrelation is \(\left\lceil\frac{(km-n)k}{(km-1)n}\right\rceil\) and an \(m\)-set is optimal if it attains this lower bound. In the reviewed paper the authors consider as alphabet the space \(\mathbb{F}_p^2\) and as words sequences within elliptic curves over the prime field \(\mathbb{F}_p\) whose lengths \(m\) divide the group order of the curve. It is shown that peak auto-correlation of the corresponding Legendre arrays has the form \(m(p^2-1)\) and that their non-peak auto-correlation values are \(kp^2-m\) for values of \(k\) up to 3 and, in many cases up to 2. In order to prove these results, the polynomial ideal containing the elliptic curve addition is considered and a corresponding Gröbner basis is calculated. Certainly, this construction provides near-optimal arrays. An own feature of this construction is its linear time-complexity. The paper is self contained and the proposed method is fully explained.