A LINEAR COMPLEXITY ANALYSIS OF QUADRATIC RESIDUES AND PRIMITIVE ROOTS SPACINGS
Mihai Caragiu, Shannon M. Tefft, Aaron Kemats, Travis Maenle · Far East Journal of Mathematical Education · 2019
We investigate the linear complexities of the periodic 0 – 1 infinite sequences in which the periods are the sequence of the parities of the spacings between quadratic residues modulo a prime p, and the sequence of the parities of the spacings between primitive roots modulo p, respectively. In either case, the Berlekamp-Massey algorithm running on MAPLE computer algebra software shows very good to perfect linear complexities. The computational results provided in this paper were the output of a 1-credit class on Computational Number Theory offered at Ohio Northern University in the Fall Semester of the academic year 2018-2019.