Breadcrumbs Section. Click here to navigate to respective pages.

Chapter

Chapter

# Schnorr’s Algorithm

DOI link for Schnorr’s Algorithm

Schnorr’s Algorithm book

# Schnorr’s Algorithm

DOI link for Schnorr’s Algorithm

Schnorr’s Algorithm book

## ABSTRACT

This chapter discusses Schnorr’s paper [123] which introduced a one-parameter family of lattice basis reduction algorithms interpolating between the LLL algorithm [88] and Kannan’s algorithm [70, 71] for a Hermite-reduced basis. For an n-dimensional lattice L ⊂ Zn and a fixed integer k ≥ 2, Schnorr’s algorithm repeatedly applies Hermite reduction to blocks of length k in the lattice basis b1,b2, . . . ,bn ∈ Zn. For k = 2, the algorithm is equivalent to LLL reduction; for k = n, the algorithm is equivalent to Hermite reduction. Schnorr’s algorithm outputs a (nonzero) vector x ∈ L for which

|x|2 ≤ (6k2)n/kΛ1(L)2, where Λ1(L) is the first minimum of L. If B is an upper bound for |b1|2, |b2|2, . . . , |bn|2 then the complexity of Schnorr’s algorithm is given by

O ( n2(kk/2+o(k) + n2) logB

) ,

arithmetic operations on integers with O(n logB) binary digits. The basic idea of the LLL algorithm is to repeatedly perform the Gaussian

algorithm on sublattices of dimension 2. The output of the Gaussian algorithm is a Hermite-reduced basis of a 2-dimensional lattice (Exercise 12.1). The basic idea of Schnorr’s algorithm is that this strategy can be generalized, using Kannan’s algorithm for Hermite reduction, to repeatedly compute a Hermitereduced basis for sublattices of dimension k, where k is any integer ≥ 2.