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

Yuri Borissov; Moon Ho Lee; Svetla Nikova

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 $θ (n) = \frac{λ_{2} (n)}{ψ_{2} (n)}$ , where $λ_{2} (n)$ is the number of primitive polynomials and $ψ_{2} (n)$ is the number of irreducible polynomials in $G F (2) [x]$ of degree $n$ . %and $2 n$ , for an arbitrary odd number $n$ . Let $n = \prod_{i = 1}^{ℓ} p_{i}^{r_{i}}$ be the prime factorization of $n$ , where $p_{i}$ are odd primes. We show that tends to 1 and is asymptotically not less than 2/3 when are fixed and tend to infinity. We also, describe an infinite series of values such that is strictly less than .

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: 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},
      url = {https://eprint.iacr.org/2007/301}
}