Tutkijamme @YoussefElHousn3 juuri julkaissut uuden artikkelin: "Nopeat kuutiojuuret Fp2:ssa algebraisen toruksen kautta." Puretaanpa tämä johonkin hieman helpommin sulattavaan.

Kuvittele, että olet Etelä-Pariisissa ja sinun täytyy päästä ravintolaan Pohjois-Pariisissa. Tähän asti vakiomenetelmä oli ajaa suoraan kaupungin keskustan läpi (Fp2) – "monimutkaisessa maailmassa", jossa jokainen laskenta maksaa ~3× enemmän liikennevalojen ja pysäkkien vuoksi. Mennäänkö suoraan keskustaan? Se on hidasta, kallista ja tehotonta.

Youssef kulkee toista reittiä: périphériquea (kehätietä). Matemaattisesti hän projisoi ongelman algebralliseen torukseen T2(Fp), rakenteeseen, jonka jälki elää kokonaan Fp:ssä – "yksinkertaisessa maailmassa". Siellä hän käyttää Lucas-sekvenssejä kuution juuren laskemiseen, jossa jokainen vaihe on yksi halpa operaatio kolmen sijaan. Ohittamalla keskustan säästät aikaa, kustannuksia ja tehokkuutta.

Nyt mielenkiintoinen osa: löytää tarkka ravintola. Lopuksi sinun täytyy ottaa oikea liittymä kehätieltä. Tämä on toipumisvaihe. Yhdistät normin N(x) kuutiojuuren ja sijaintisi toruksella (molemmat laskettu Fp:ssä) rekonstruoidaksesi tarkat koordinaatit takaisin Fp2:ssa. N(x):n kuutiojuuren laskeminen Fp:ssä ei ole halpaa. Mutta Youssef laskee sen lähes ilmaiseksi toruksen projektion aikana ja tallentaa sen myöhempää varten. Se on kuin muistaisit poistumisreitin heti kun astut kehätielle.

Mitä tämä siis oikeastaan saavuttaa? Tällä lähestymistavalla Youssef nopeuttaa kuutiojuurilaskentaa jopa 2.1× – ydintoiminto, jota käytetään ZK-pisteen dekompressiossa, hash-to-curve- ja post-quantum isogeneys -protokollissa.