On the probability of generating a lattice (Q2437315)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On the probability of generating a lattice |
scientific article |
Statements
On the probability of generating a lattice (English)
0 references
3 March 2014
0 references
Motivated by an analysis of the success probability of quantum algorithms for solving the discrete logarithm problem in infrastructures obtained from number fields, the paper under review studies the problem of determining the probability that \(m\) vectors selected uniformly at random from \({\mathcal L} \cap [0,B)^n\) generate the (full-rank) lattice \({\mathcal L} \subset {\mathbb R^n}\), when \(B\) is chosen appropriately large. To state the main theorem precisely, assume that \(B \geq 8 n^{ n \over 2 } \nu({\mathcal L})\) and \(B_1 \geq 8 n^2 (n+1) B\), where \(\nu({\mathcal L})\) is the covering radius of \(\mathcal L\) (i.e., the smallest \(r\) such that translates by \(\mathcal L\) of a ball of radius \(r\) covers \({\mathbb R}^n\)), and that \(n\) vectors are selected uniformly at random from \({\mathcal L} \cap [0,B)^n\) and \(n+1\) vectors from \({\mathcal L} \cap [0,B)^n\). If the vectors are sampled independently then the probability that they generate \(\mathcal L\) is at least \[ \left( \prod_{ j=2 }^{ n+1 } \zeta(j)^{ -1 } - {1 \over 4} \right) \prod_{ k=0 }^{ n-1 } \left( 1 - n^{ k \over 2 } {{ \left( 4 n^{ n \over 2 } + 1 \right)^k } \over { \left( 4 n^{ n \over 2 } - 1 \right)^n }} \right) . \] This means that \(2n+1\) vectors suffice to generate \(\mathcal L\) with constant probability, provided that \(B\) is chosen sufficiently large. The authors conjecture that the quantity \(2n+1\) in this statement can be replaced by \(n+1\).
0 references
Random generation of a lattice
0 references
Riemann zeta function
0 references
analysis of quantum algorithm
0 references
discrete logarithm problem
0 references
0 references