Mřížová redukce - Lattice reduction

Redukce mřížky ve dvou rozměrech: černé vektory jsou daným základem pro mřížku (představovanou modrými tečkami), červené vektory jsou redukovanou bází

V matematice je cílem mřížková redukce základu je dáno celé číslo mříž jako vstup, najít a základ s krátkým, téměř ortogonální vektory. To je realizováno pomocí různých algoritmů, jejichž doba běhu je obvykle alespoň exponenciální v dimenzi mřížky.

Téměř ortogonální

Jedno opatření téměř ortogonální je vada ortogonality. Porovná se součin délek základních vektorů s objemem rovnoběžnostěn oni definují. Pro dokonale ortogonální bazální vektory by tyto veličiny byly stejné.

Jakýkoli konkrétní základ ${displaystyle n}$ vektory mohou být reprezentovány a matice ${displaystyle B}$, jehož sloupce jsou základními vektory ${displaystyle b_ {i}, i = 1, ldots, n}$. V plně dimenzionální v případě, že se počet základních vektorů rovná dimenzi prostoru, který zabírají, je tato matice čtvercová a objem základního rovnoběžnostěnu je prostě absolutní hodnota určující této matice ${displaystyle det (B)}$. Pokud je počet vektorů menší než rozměr podkladového prostoru, pak objem je ${displaystyle {sqrt {det (B ^ {T} B)}}}$. Pro danou mříž ${displaystyle Lambda}$, tento objem je stejný (až k podpisu) pro jakýkoli základ, a proto se označuje jako determinant mřížky ${displaystyle det (Lambda)}$ nebo mřížková konstanta ${displaystyle d (lambda)}$.

Porucha ortogonality je součinem délek základních vektorů dělených objemem rovnoběžnostěnu;

${displaystyle delta (B) = {frac {Pi _ {i = 1} ^ {n} | b_ {i} |} {sqrt {det (B ^ {T} B)}}} = {frac {Pi _ { i = 1} ^ {n} | b_ {i} |} {d (Lambda)}}}$

Z geometrické definice to lze ocenit ${displaystyle delta (B) geq 1}$ s rovností právě tehdy, když je základ ortogonální.

Pokud je problém s redukcí mřížky definován jako nalezení základu s nejmenší možnou vadou, pak problém je NP-tvrdé. Existují však polynomiální čas algoritmy k nalezení základu s vadou ${displaystyle delta (B) leq c}$ kde C je nějaká konstanta závislá pouze na počtu bazických vektorů a dimenzi podkladového prostoru (pokud se liší). Toto je dost dobré řešení v mnoha praktických aplikacích.

Ve dvou rozměrech

Pro základ skládající se pouze ze dvou vektorů existuje jednoduchá a účinná metoda redukce, která je velmi analogická s Euklidovský algoritmus pro největší společný dělitel dvou celých čísel. Stejně jako u euklidovského algoritmu je metoda iterativní; v každém kroku je větší ze dvou vektorů snížen přidáním nebo odečtením celočíselného násobku menšího vektoru.

Pseudokód algoritmu, často známý jako Lagrangeův algoritmus nebo Lagrange-Gaussův algoritmus, je následující:

    Vstup: ${extstyle (u, v)}$ základ pro mříž ${extstyle L}$. Předpokládat, že ${extstyle || v || leq || u ||}$, jinak je vyměňte. Výstup: Základ ${extstyle (u, v)}$ s ${extstyle || u || = lambda _ {1} (L), || v || = lambda _ {2} (L)}$.

    Zatímco ${extstyle || v || leq || u ||}$:         ${extstyle q: = lfloor {langle u, {frac {v} {|| v || ^ {2}}} úhel} ceil}$         ${extstyle r: = u-qv}$         ${extstyle u: = v}$         ${extstyle v: = r}$

Viz část o Lagrangeově algoritmu v ^[1] pro další detaily.

Aplikace

Algoritmy mřížkové redukce se používají v řadě moderních číselných teoretických aplikací, včetně objevu a algoritmus čepu pro ${displaystyle pi}$. Ačkoli stanovení nejkratší základny je možná problém NP-úplný, algoritmy, jako je Algoritmus LLL^[2] může najít krátký (ne nutně nejkratší) základ v polynomiálním čase se zaručeným výkonem v nejhorším případě. JÁ BUDU je široce používán v dešifrování z veřejný klíč kryptosystémy.

Při použití k nalezení celočíselných vztahů se typický vstup do algoritmu skládá z rozšířeného ${displaystyle n}$ X ${displaystyle n}$ matice identity s položkami v posledním sloupci skládající se z ${displaystyle n}$ prvků (vynásobeno velkou kladnou konstantou ${displaystyle w}$ k penalizaci vektorů, které nesčítají nulu), mezi nimiž je vztah hledán.

The Algoritmus LLL pro výpočet byla použita téměř ortogonální základna celočíselné programování v jakékoli pevné dimenzi lze provést v polynomiální čas.^[3]

Algoritmy

Následující algoritmy snižují mřížkové základny; je zde také uvedeno několik veřejných implementací těchto algoritmů.

Reference