Neliöresiduut

Neliöresiduut ovat keskeinen käsite lukuteoriassa. Neliöresiduaa määritellään kokonaisluvuksi, joka on jaollinen tietyllä luvulla modulo jokin toinen luku. Tarkemmin sanottuna, kokonaislukua a kutsutaan neliöresiduksi modulo n, jos on olemassa sellainen kokonaisluku x, että x² ≡ a (mod n). Toisin sanoen, x² ja a antavat saman jakojäännöksen jaettaessa luvulla n. Jos tällaista x ei ole olemassa, a on neliöepäresidua.

Neliöresidujen tutkimus liittyy läheisesti yleiseen kongruenssiin ja sen ratkaisemiseen. Esimerkiksi, kun tarkastellaan kongruenssia x² ≡ a (mod p), missä p on alkuluku, katsotaan onko a neliöresidua modulo p. Jos a on neliöresidua ja a ei ole jaollinen p:llä, kongruenssilla on täsmälleen kaksi ratkaisua modulo p. Jos a on neliöepäresidua, kongruenssilla ei ole ratkaisuja. Jos a on jaollinen p:llä, a ≡ 0 (mod p), ja a on neliöresidua, jolla on täsmälleen yksi ratkaisu x ≡ 0 (mod p).

Neliöresidujen ominaisuuksia tutkitaan usein käyttämällä Eulerin kriteriota alkulukuja modulo. Eulerin kriterio koskee neliöresidua modulo paritonta alkulukua p. Se sanoo, että jos p on pariton alkuluku ja a ei ole jaollinen p:llä, niin a on neliöresidua modulo p jos ja vain jos a^((p-1)/2) ≡ 1 (mod p). Jos a^((p-1)/2) ≡ -1 (mod p), niin a on neliöepäresidua modulo p.

Neliöresiduilla on sovelluksia kryptografiassa, esimerkiksi Legendre-symbolin ja Jacobi-symbolin avulla, jotka liittyvät neliöresidujen olemassaoloon. Niiden avulla voidaan luoda ja purkaa salakirjoitusta.