International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

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

Authors:
Yuri Borissov
Moon Ho Lee
Svetla Nikova
Download:
URL: http://eprint.iacr.org/2007/301
Search ePrint
Search Google
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}$.
BibTeX
@misc{eprint-2007-13581,
  title={On Asymptotic Behavior of the Ratio Between the Numbers of Binary Primitive and Irreducible Polynomials},
  booktitle={IACR Eprint archive},
  keywords={},
  url={http://eprint.iacr.org/2007/301},
  note={Extended abstract of a talk at Finite Fields and applications (FQ8), Melbourne, Australia, July 2007 svetla.nikova@esat.kuleuven.be 13740 received 2 Aug 2007, last revised 15 Aug 2007},
  author={Yuri Borissov and Moon Ho Lee and Svetla Nikova},
  year=2007
}