Block Korkin–Zolotarev Bases and Successive Minima
Block Korkin–Zolotarev Bases and Successive Minima
复制标题
阻止 Korkin-Zolotarev 基底和连续最小值
DOI：
10.1590/s0074-02761996000100006
复制
发表时间：
1992
影响因子：
2.8
通讯作者：
InformatikFebruary
中科院分区：
文献类型：
--
作者：
SuccessiveMinimaC;P.;SchnorrUniversitt;FrankfurtFachbereich;Mathematik;InformatikFebruary
设 b1, . 。 。 , bm ∈ IR 是格 L 的任意基，它是块大小为 β 的块 Korkin-Zolotarev 基，并让 λi(L) 表示格 L 的连续最小值。我们证明，对于 i = 1，. 。 。 , m 4 i + 3 γ −2 i−1 β−1 β ≤ ‖bi‖/λi(L) ≤ γ 2 m−i β−1 β i + 3 4 其中γβ 是埃尔米特常数。对于 β = 3，我们建立最佳上限 ‖b1‖/λ1(L) ≤ ( 3 2 )m−1 2 −1 ，并且我们提出了该边界是紧的块 Korkin-Zolotarev 晶格基。我们使用块 Korkin-Zolotarev 基改进了 Babai (1986) 的最近平面算法。给定一个块 Korkin-Zolotarev 基 b1，. 。 。 , bm ，块大小为 β，x ∈ L(b1, . . . , bm) 可以在时间 β 中找到满足 ‖x−v‖2 ≤ mγ 2m β−1 β minu∈L ‖x− u‖2 的格点 v。
Let b1, . . . , bm ∈ IR be an arbitrary basis of lattice L that is a block Korkin–Zolotarev basis with block size β and let λi(L) denote the successive minima of lattice L. We prove that for i = 1, . . . , m 4 i + 3 γ −2 i−1 β−1 β ≤ ‖bi‖/λi(L) ≤ γ 2 m−i β−1 β i + 3 4 where γβ is the Hermite constant. For β = 3 we establish the optimal upper bound ‖b1‖/λ1(L) ≤ ( 3 2 )m−1 2 −1 and we present block Korkin–Zolotarev lattice bases for which this bound is tight. We improve the Nearest Plane Algorithm of Babai (1986) using block Korkin–Zolotarev bases. Given a block Korkin–Zolotarev basis b1, . . . , bm with block size β and x ∈ L(b1, . . . , bm) a lattice point v can be found in time β satisfying ‖x−v‖2 ≤ mγ 2m β−1 β minu∈L ‖x− u‖2.