The discrete logarithm is an integer k that solves the equation bk=g, where b and g are elements of a group. For example, consider the equation 3k ≡ 13 (mod 17) for k, which has a solution 4. Finding the discrete logarithm of such an equation is known as the discrete logarithm problem. No efficient solution is known for this problem using a conventional algorithm. Integer factorization is another problem that has immense potential in areas such as security and cryptography with no known efficient algorithm on a conventional computer. A quantum computer (which is theoretically similar to nondeterministic machines, and at a very early phase of development), on the other hand, can solve these problems in polynomial time. Interested readers may check Peter Shor’s article [1] for details. In the current paper, Fontein and Wocjan address a problem that plays a vital role in the analysis of the success probability of quantum algorithms for solving the discrete logarithm problem.
The authors study the problem of “determining the probability that m vectors selected uniformly at random from the intersection of the full-rank lattice in Rn and the window [0,B)n generate when B is chosen to be appropriately large.” For readers not familiar with the terms, let b1,b2, … ,br (with r ≤ n) be a linearly independent set of rows in Rn. Then, the lattice generated by the basis b1,b2, … ,br is the set . Here, has dimension n and rank r. If n=r, then has full rank.
The authors provide a complete proof that m=2n+1 using two windows, given B is chosen to be sufficiently large in terms of n and the covering radius of and the last n+1 vectors are sampled from a slightly larger window. Based on extensive computer simulations, they conjecture that m=n+1 uses only a single window.
This paper contains substantial mathematical content, and I would recommend it for advanced graduate students and researchers in mathematics and theoretical computer science.
