Korkine–Zolotarev lattice basis reduction algorithm

<p>The Korkine–Zolotarev (KZ) lattice basis reduction algorithm or Hermite–Korkine–Zolotarev (HKZ) algorithm is a <a href="/facts/Lattice_reduction/Mrz9g9oc">lattice reduction</a> <a href="/facts/Algorithm/fnl5NmRt">algorithm</a>.
</p><p>For lattices in 
  
    
      
        
          
            R
          
          
            n
          
        
      
    
    {\displaystyle \mathbb {R} ^{n}}
  
 it yields a lattice basis with orthogonality defect at most 
  
    
      
        
          n
          
            n
          
        
      
    
    {\displaystyle n^{n}}
  
, unlike the 
  
    
      
        
          2
          
            
              n
              
                2
              
            
            
              /
            
            2
          
        
      
    
    {\displaystyle 2^{n^{2}/2}}
  
 bound of the <a href="/facts/Lenstra%25E2%2580%2593Lenstra%25E2%2580%2593Lov%25C3%25A1sz_lattice_basis_reduction_algorithm/hadYSXGw">LLL reduction</a>. KZ has exponential complexity versus the polynomial complexity of the <a href="/facts/Lenstra%25E2%2580%2593Lenstra%25E2%2580%2593Lov%25C3%25A1sz_lattice_basis_reduction_algorithm/hadYSXGw">LLL reduction</a> algorithm, however it may still be preferred for solving multiple <a href="/facts/Closest_vector_problem/YHXNNrrG">closest vector problems</a> (CVPs) in the same lattice, where it can be more efficient.
</p>

Korkine–Zolotarev lattice basis reduction algorithm open-in-new

Korkine–Zolotarev lattice basis reduction algorithm