Hamming distance from irreducible polynomials over $\mathbb {F}_2$

Abstract : We study the Hamming distance from polynomials to classes of polynomials that share certain properties of irreducible polynomials. The results give insight into whether or not irreducible polynomials can be effectively modeled by these more general classes of polynomials. For example, we prove that the number of degree $n$ polynomials of Hamming distance one from a randomly chosen set of $\lfloor 2^n/n \rfloor$ odd density polynomials, each of degree $n$ and each with non-zero constant term, is asymptotically $(1-e^{-4}) 2^{n-2}$, and this appears to be inconsistent with the numbers for irreducible polynomials. We also conjecture that there is a constant $c$ such that every polynomial has Hamming distance at most $c$ from an irreducible polynomial. Using exhaustive lists of irreducible polynomials over $\mathbb{F}_2$ for degrees $1 ≤ n ≤ 32$, we count the number of polynomials with a given Hamming distance to some irreducible polynomial of the same degree. Our work is based on this "empirical" study.
Type de document :
Communication dans un congrès
Jacquet, Philippe. 2007 Conference on Analysis of Algorithms, AofA 07, 2007, Juan les Pins, France. Discrete Mathematics and Theoretical Computer Science, DMTCS Proceedings vol. AH, 2007 Conference on Analysis of Algorithms (AofA 07), pp.183-196, 2007, DMTCS Proceedings
Liste complète des métadonnées

Littérature citée [7 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01184798
Contributeur : Coordination Episciences Iam <>
Soumis le : lundi 17 août 2015 - 17:00:20
Dernière modification le : vendredi 1 juin 2018 - 15:24:01
Document(s) archivé(s) le : mercredi 18 novembre 2015 - 12:18:32

Fichier

dmAH0113.pdf
Fichiers éditeurs autorisés sur une archive ouverte

Licence


Distributed under a Creative Commons Paternité 4.0 International License

Identifiants

  • HAL Id : hal-01184798, version 1

Collections

Citation

Gilbert Lee, Frank Ruskey, Aaron Williams. Hamming distance from irreducible polynomials over $\mathbb {F}_2$. Jacquet, Philippe. 2007 Conference on Analysis of Algorithms, AofA 07, 2007, Juan les Pins, France. Discrete Mathematics and Theoretical Computer Science, DMTCS Proceedings vol. AH, 2007 Conference on Analysis of Algorithms (AofA 07), pp.183-196, 2007, DMTCS Proceedings. 〈hal-01184798〉

Partager

Métriques

Consultations de la notice

211

Téléchargements de fichiers

160