Paper 2007/301

On Asymptotic Behavior of the Ratio Between the Numbers of Binary Primitive and Irreducible Polynomials

Yuri Borissov, Moon Ho Lee, and Svetla Nikova

Abstract

In this paper we study the ratio $\theta(n) = \frac{\lambda_2(n)}{\psi_2(n)}$, where ${\lambda_2(n)}$ is the number of primitive polynomials and ${\psi_2(n)}$ is the number of irreducible polynomials in $GF(2)[x]$ of degree $n$. %and $2n$, for an arbitrary odd number $n$. Let $n=\prod_{i=1}^{\ell} p_i^{r_i}$ be the prime factorization of $n$, where $p_i$ are odd primes. We show that $\theta(n)$ tends to 1 and $\theta(2n)$ is asymptotically not less than 2/3 when $r_i$ are fixed and $p_i$ tend to infinity. We also, describe an infinite series of values $n_{s}$ such that $\theta(n_{s})$ is strictly less than $\frac{1}{2}$.

Metadata
Available format(s)
PDF
Publication info
Published elsewhere. Extended abstract of a talk at Finite Fields and applications (FQ8), Melbourne, Australia, July 2007
Contact author(s)
svetla nikova @ esat kuleuven be
History
2007-08-15: revised
2007-08-07: received
See all versions
Short URL
https://ia.cr/2007/301
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2007/301,
      author = {Yuri Borissov and Moon Ho Lee and Svetla Nikova},
      title = {On Asymptotic Behavior of the Ratio Between the Numbers of Binary Primitive and Irreducible Polynomials},
      howpublished = {Cryptology ePrint Archive, Paper 2007/301},
      year = {2007},
      note = {\url{https://eprint.iacr.org/2007/301}},
      url = {https://eprint.iacr.org/2007/301}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.