Skip to Main content Skip to Navigation
Preprints, Working Papers, ...

Counting Co-Cyclic Lattices

Phong Q. Nguyen 1, 2 Igor E. Shparlinski 3
2 CRYPT - Cryptanalyse
LIAMA - Laboratoire Franco-Chinois d'Informatique, d'Automatique et de Mathématiques Appliquées, Inria Paris-Rocquencourt
Abstract : There is a well-known asymptotic formula, due to W. M. Schmidt (1968) for the number of full-rank integer lattices of index at most $V$ in $\mathbb{Z}^n$. This set of lattices $L$ can naturally be partitioned with respect to the factor group $\mathbb{Z}^n/L$. Accordingly, we count the number of full-rank integer lattices $L \subseteq \mathbb{Z}^n$ such that $\mathbb{Z}^n/L$ is cyclic and of order at most $V$, and deduce that these co-cyclic lattices are dominant among all integer lattices: their natural density is $\left(\zeta(6) \prod_{k=4}^n \zeta(k)\right)^{-1} \approx 85\%$. The problem is motivated by complexity theory, namely worst-case to average-case reductions for lattice problems.
Document type :
Preprints, Working Papers, ...
Complete list of metadata

https://hal.inria.fr/hal-01256022
Contributor : Phong Q. Nguyen <>
Submitted on : Thursday, January 14, 2016 - 11:45:04 AM
Last modification on : Wednesday, June 2, 2021 - 3:39:52 AM

Links full text

Identifiers

  • HAL Id : hal-01256022, version 1
  • ARXIV : 1505.06429

Collections

Citation

Phong Q. Nguyen, Igor E. Shparlinski. Counting Co-Cyclic Lattices. 2015. ⟨hal-01256022⟩

Share

Metrics

Record views

393