Modulajuurista

Modulajuurista tarkoittaa lukujen x ratkaisuja yhtälöön x^k ≡ a (mod n). Kun puhutaan modulaarisista juurista, etsitään k:nnen juuria, eli x, jotka nollahavaitsevat tälle kongruenssille. Ongelman ratkaisu riippuu usein modulusn rakenteesta: pienempiä jäännöslukujen ryhmiä sekä kiinalaisen jäännöslauseen avulla voidaan ratkaista per modulus ja yhdistää tulokset.

Jos n on yksinkertaisesti prime p, yksikköjen ryhmä modulo p on kreikkalainen, ryhmän koko on p−1 ja on mahdollisuus ratkaista x^k ≡ a mod p ryhmän rakenteen avulla. Tällöin ratkaisut ovat joko 0 tai gcd(k, p−1) kappaletta, riippuen siitä, onko a oikeasti k:nnen neliöjuuren tai yleisemmän k:nnen juuren kuvatun kuvan jäsen. Käytännössä voidaan merkitä, että a on k:nnen juuren modulo p, jos a^{(p−1)/d} ≡ 1 (mod p), missä d = gcd(k, p−1).

Monimutkaisemmissa moduloissa, erityisesti kun n on epäprimaarinen tai kun a ei ole yksikkö modulo n, ratkaisut ratkaistaan jakamalla ongelma p^e-per modulus ja yhdistämällä tulokset kiinalaisella jäännöslainilla (CRT). Tällöin voidaan käsitellä sekä yksikköjä että n:n tekijöihin liittyviä erityistapauksia.

Computationally voidaan käyttää erilaisia menetelmiä. Yksi erikoistapaus on neliöjuurten löytäminen mod primeille (Tonelli–Shanks); perus Henselin liftingillä voidaan siirtyä primeista korkeampiin potensseihin. Yleisemmissä tapauksissa ratkaisuja etsitään kiertämällä k-juurien kuvasuhteita, mahdollisesti diskreetin logaritmin tai brutaalituloksen avulla, ja yhdistämällä ratkaisut CRT:n avulla.

Esimerkkitapaus: ratkaistaan x^2 ≡ 2 (mod 7). Testaamalla luvut 0–6 saadaan x ≡ 3 tai x ≡ 4, koska sekä 3^2 että 4^2 antavat 2 mod 7. Modulajuurien ratkaisuja sovelletaan lukuteoriassa ja kryptografiassa sekä teoreettisessa tutkimuksessa.