Korkine–Zolotarev gitterbasreduktionsalgoritm

Ej att förväxla med Kolmogorov-Zurbenko-filter .

Korkine –Zolotarev (KZ ) gitterbasreduktionsalgoritm eller Hermite-Korkine–Zolotarev (HKZ) algoritm är en gitterreduktionsalgoritm .

För gitter i $\mathbb {R} ^{n}$ ger det en gitterbas med ortogonalitetsdefekt som mest ${\displaystyle n^{n}} ,$ till skillnad från $2 ^{n/2}$ gräns för LLL-reduktionen . KZ har exponentiell komplexitet kontra polynomkomplexiteten för LLL-reduktionsalgoritmen , men den kan fortfarande vara att föredra för att lösa sekvenser av närmaste vektorproblem (CVP) i ett gitter, där det kan vara mer effektivt.

Historia

Definitionen av en KZ-reducerad bas gavs av A. Korkine och G. Zolotareff 1877, en förstärkt version av Hermite-reduktion. Den första algoritmen för att konstruera en KZ-reducerad bas gavs 1983 av Kannan.

Algoritmen Block Korkine-Zolotarev (BKZ) introducerades 1987.

Definition

En KZ-reducerad grund för ett gitter definieras enligt följande:

Givet en grund

$\mathbf {B} =\{\mathbf {b} _{1},\mathbf {b} _{2},\dots ,\ mathbf {b} _{n}\},$

definiera sin Gram-Schmidt-process ortogonala grund

$\mathbf {B} ^{*}=\{\mathbf {b} _{1}^{*},\mathbf {b} _{2}^{*},\dots ,\mathbf {b} _{n}^{*}\},$

och Gram-Schmidt-koefficienterna

$\mu _{i,j}={\frac {\langle \mathbf {b} _{i}, \mathbf {b} _{j}^{*}\rangle }{\langle \mathbf {b} _{j}^{*},\mathbf {b} _{j}^{*}\rangle }}$ , för valfri $1\leq j<i\leq n$ .

Definiera även projektionsfunktioner

$\pi _{i}(\mathbf {x} )=\summa _{ j\geq i}{\frac {\langle \mathbf {x} ,\mathbf {b} _{j}^{*}\rangle }{\langle \mathbf {b} _{j}^{*}, \mathbf {b} _{j}^{*}\rangle }}\mathbf {b} _{j}^{*}$

som projicerar $\mathbf {x}$ ortogonalt på spännvidden av $\mathbf {b} _{i}^{*},\cdots ,\mathbf {b } _{n}^{*}$ .

Då är basen $B$ KZ-reducerad om följande gäller:

1. $\mathbf {b} _{i}^{*}$ är den kortaste vektorn som inte är noll i $\pi _{i}({\mathcal {L} }(\mathbf {B} ))$
2. För alla $j<i$ , $\left|\mu _{i,j}\right|\leq 1/2$

Observera att det första villkoret kan omformuleras rekursivt som att $\mathbf {b} _{1}$ är den kortaste vektorn i gittret, och ${\displaystyle \{\pi _{2}(\mathbf {b} _{2}),\cdots \pi _{2}(\mathbf {b} _{n})\}} är en$ KZ -reducerad bas för gittret $\pi _{2}({\mathcal {L}}(\mathbf {B} ))$ .

Observera också att det andra villkoret garanterar att den reducerade basen är längdreducerad (att lägga till en heltalsmultipel av en basvektor till en annan kommer inte att minska dess längd); samma villkor används i LLL-reduktionen.

Anteckningar

•   Korkine, A.; Zolotareff, G. (1877). "Sur les formes quadratiques positiva" . Matematiska Annalen . 11 (2): 242–292. doi : 10.1007/BF01442667 . S2CID 121803621 .

• Lyu, Shanxiang; Ling, Cong (2017). "Boostade KZ- och LLL-algoritmer". IEEE-transaktioner på signalbehandling . 65 (18): 4784–4796. arXiv : 1703.03303 . Bibcode : 2017ITSP...65.4784L . doi   : 10.1109/TSP.2017.2708020 . S2CID 16832357 .

• Wen, Jinming; Chang, Xiao-Wen (2018). "Om KZ-minskningen". arXiv : 1702.08152 . {{ citera journal }} : Citera journal kräver |journal= ( hjälp )

•   Micciancio, Daniele; Goldwasser, Shafi (2002). Gitterproblemens komplexitet . s. 131–136. doi : 10.1007/978-1-4615-0897-7 . ISBN 978-1-4613-5293-8 .

•   Zhang, Wen; Qiao, Sanzheng; Wei, Yimin (2012). "HKZ och Minkowski-reduktionsalgoritmer för gitterreduktionsstödd MIMO-detektion" ( PDF) . IEEE-transaktioner på signalbehandling . 60 (11): 5963. Bibcode : 2012ITSP...60.5963Z . doi : 10.1109/TSP.2012.2210708 . S2CID 5962834 .