Modulajuurien

Modulajuurien ovat kokonaislukuarvojen juuria siinä modulaattorissa, jonka mukaan ratkaistava yhtälö on f(x) ≡ 0 (mod m). Toisin sanoen modulajuurit ovat sellaisia x-kokonaisuuksia, jotka vastaavat reaalimaailmassa ihmisosumien tai polynomiyhtälöiden ratkaisuja, mutta huomioiden luvun m ja luvun jäännöksen. Modulaariin arvoon kuuluvat jäännökset ovat 0, 1, ..., m-1, ja moduulilla m on useita mahdollisia ratkaisuja sekä monimutkaisempia rakenneosia kuin todellisiin lukuihin liittyvät juuret.

Ominaisuudet ja laskentaperiaatteet. Yhtälön f(x) ≡ 0 (mod m) ratkaisuja voidaan usein käsitellä kiinteän m:n primaarifaktorisoinnin kautta. Jos m = p1^e1 · p2^e2 · ... · pk^ek, modulajuurit voidaan johtaa toisen moduulin juurista käyttäen Yhdistelmässääntöä (Chinese remainder theorem). Yhtälön ratkaisuja voi syntyä vain, jos kyseiset juuret esiintyvät kaikilla tekijämoduuleilla yhteensopivasti. Yleensä primaarimoduulien yli juurien määrä on rajoitettu polynomiyhtälön asteeseen, ja Henselin lavastus mahdollistaa juurien etenemisen kohti suurempia potensseja.

Laskentamenetelmät. Modulaaristen juurien etsiminen alkaa usein ydinongelmasta f(x) mod p, jossa p on prime. Siellä käytetään polynomifaktorointia modulo p ja mahdollisesti Henselin lemmaa p^k-rajuille, jotta juuret siirretään moduuliin p^k. Lisäksi käytetään yleisiä algoritmeja, kuten CRT:n ratkaisuja, sekä tarvittaessa polynomifaktorointia modulo primeihin. Yleiskäytännössä laskenta koostuu sekä kiinteän modulin jakautumisesta pienempiin osiin että juurien yhdistämisestä oikein koko m:n tasolla.

Esimerkki. Esitäen x^2 ≡ 2 (mod 7) tarkoittaa, että x ≡ 3 tai x ≡ 4 modulo 7, jolloin kummatkin luvut ovat modulajuuria.

Sovellukset. Modulajuuria tarvitaan lukuteoreettisissa tehtävissä, kryptografisissa algoritmeissa sekä virheenkorjauksessa ja koodauksessa, joissa ratkaisuja on löydettävä modulo tiettyjen lukujen.

Historia ja suhteet. Ajatus modulaarisista juurista juontaa juurensa klassiseen lukuteoriaan; Henselin lemmaa ja Yhdistäessä käytetyt menetelmät ovat keskeisiä keinoja siirtää juuria pienemmistä moduuleista suurempiin.