## Cryptology ePrint Archive: Report 2007/301

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

*Yuri Borissov and 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}$.

**Category / Keywords: **

**Publication Info: **Extended abstract of a talk at Finite Fields and applications (FQ8), Melbourne, Australia, July 2007

**Date: **received 2 Aug 2007, last revised 15 Aug 2007

**Contact author: **svetla nikova at esat kuleuven be

**Available format(s): **PDF | BibTeX Citation

**Version: **20070815:073802 (All versions of this report)

**Discussion forum: **Show discussion | Start new discussion

[ Cryptology ePrint archive ]