Võre redutseerimise demonstratsioon

Mis see tööriist teeb?

See tööriist demonstreerib kahemõõtmelise võre redutseerimise põhimõtet. Sa sisestad kaks lineaarselt sõltumatut täisarvulist baasvektorit ja täisarvulise kordajate vahemiku. Tööriist otsib süstemaatiliselt kõik mittekahanevad kordajate paarid (i, j) vahemikus -range kuni +range ja arvutab vektori i*v1 + j*v2 pikkuse. Seejärel kuvab ta lühima leitud vektori, selle kordajad ja pikkuse.

Konkreetne näide

Oletame, et sisestad v1 = (2, 1) ja v2 = (1, 2) ning vahemikuks 5. Tööriist kontrollib kõik paarid (i, j) vahemikus -5 kuni 5. Näiteks paar (1, -1) annab vektori (1, -1), mille pikkus on ruutjuur 2-st ≈ 1.41421. Tööriist leiab selle lühima vektori ja kuvab tulemuse.

Kuidas tulemust tõlgendada?

Tulemus sõltub otsinguakna suurusest. Suurem vahemik kontrollib rohkem kombinatsioone, kuid võtab kauem aega. Kui on mitu võrdse pikkusega vektorit, kuvatakse ainult üks neist. See on õppeotstarbeline demonstratsioon, mitte LLL, BKZ või CVP algoritm, seega ei sobi see reaalsete krüptograafiliste parameetrite hindamiseks.

Korduma kippuvad küsimused

Miks tulemus muutub, kui suurendan vahemikku?

Kuna otsingupiirkond on piiratud, võib suurem vahemik leida lühema vektori, mida väiksemas vahemikus polnud. See näitab, et tulemus on otsinguakna suhtes tundlik.

Kas tööriist kasutab LLL algoritmi?

Ei, see on lihtne ammendav otsing kahemõõtmelises ruudustikus. See ei ole LLL, BKZ ega CVP lahendaja.

Mida tähendab "pikkus ümardatud viie kümnendkohani"?

Pikkus arvutatakse täpselt, kuid kuvatakse ümardatuna viie kümnendkohani. See on ümardamine, mitte kärpimine.

Kontrollnimekiri

• Sisesta kaks lineaarselt sõltumatut vektorit.
• Kontrolli, et koordinaadid on täisarvud vahemikus -1 000 000 kuni 1 000 000.
• Vali vahemik 1 kuni 100.
• Käivita arvutus.
• Vaata tulemust ja mõista selle sõltuvust otsinguaknast.