A linear complexity analysis of quadratic residues and primitive roots spacings

DOI10.17654/ME019010027zbMATH Open1435.11008arXiv1902.07314WikidataQ127936892 ScholiaQ127936892MaRDI QIDQ5114772FDOQ5114772

Authors: Mihai Caragiu, Shannon Tefft, Aaron Kemats, Travis Maenle 

Publication date: 26 June 2020

Published in: Far East Journal of Mathematical Education (Search for Journal in Brave)

Abstract: 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.

Full work available at URL: https://arxiv.org/abs/1902.07314

Recommendations

• On the linear complexity of binary sequences on the basis of biquadratic and sextic residue classes
• Binary sequences derived from differences of consecutive quadratic residues
• The linear complexity of binary sequences with period (2/sup n/-1)/sup k/
• Linear Complexity of Some Generalized Cyclotomic Sequences
• Linear complexity of ternary sequences formed on the basis of power residue classes

zbMATH Keywords

linear complexityprimitive rootsquadratic residuesspacingscomputational number theory

Mathematics Subject Classification ID

Congruences; primitive roots; residue systems (11A07) Power residues, reciprocity (11A15) Number-theoretic algorithms; complexity (11Y16)

Cites Work

• Title not available (Why is that?)
• Shift-register synthesis and BCH decoding
• Linear Complexity and Random Sequences
• New techniques for the computation of linear recurrence coefficients
• On the Distribution of Quadratic Residues (mod p )
• Sequential Experiments with Primes

Cited In (3)

• Comparison of algorithms to calculate quadratic irregularity of prime numbers
• First-hit analysis of algorithms for computing quadratic irregularity
• Binary sequences derived from differences of consecutive quadratic residues

Uses Software

• Maple
• PlanetMath

This page was built for publication: A linear complexity analysis of quadratic residues and primitive roots spacings

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5114772)