A Simpler Trace Representation of Legendre Sequences

Minglong QI  Shengwu XIONG  Jingling YUAN  Wenbi RAO  Luo ZHONG  

IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E98-A   No.4   pp.1026-1031
Publication Date: 2015/04/01
Online ISSN: 1745-1337
DOI: 10.1587/transfun.E98.A.1026
Type of Manuscript: LETTER
Category: Cryptography and Information Security
Legendre sequence,  quadratic residue,  quadratic non-residue,  primitive root,  pth root of unity,  

Full Text: PDF>>
Buy this Article

We found that the work of Kim et al. [1] on trace representation of the Legendre sequence with the periods p ≡ ±3 (mod 8) can be improved by restricting the selection of the periods p while maintaining the form p ≡ ±3 (mod 8) unchanged. Our method relies on forcing the multiplicative group of residue classes modulo p, Zp*, to take 2 as the least primitive root. On the other hand, by relaxing the very strong condition in the theorem of these authors and by using the product among powers of the primitive root and powers of any quadratic residue element to represent an element in Zp*, we could extend Kim's formula so that it becomes a special case of our formula more general.