A linear complexity analysis of quadratic residues and primitive roots spacings

DOI10.17654/ME019010027MaRDI QIDQ5114772zbMATH OpenWikidataFDO

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)

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

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)

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.

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

Cites work

• scientific article; zbMATH DE number 1182117 (Why is no real title available?)
• 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
• Shift-register synthesis and BCH decoding

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

Describes a project that uses

Uses Software

• PlanetMath
• Maple

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)