We all know that block Korkine-Zolotarev (BKZ) algorithm is essentially a deterministic lattice reduction algorithm. However, in the actual implementation, the BKZ algorithm contains some randomization, For example, the actual algorithm will do some random unimodular transformations on the lattice basis in order to obtain a better reduced basis. I wonder if this subtle change will make a big difference to the final output. Does it?

  • $\begingroup$ How would one quantify such difference? $\endgroup$ Jul 14 at 9:43
  • $\begingroup$ one quantity is using the length of the shortest vector in the reduced basis $\endgroup$ Jul 14 at 11:40


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.