Neliönjäännös

Matematiikassa luku q on neliönjäännös modulo n, jos on olemassa kokonaisluku x, jolle

${x^{2}}\equiv {q}{\mbox{ (mod }}n{\mbox{)}}.$

muutoin lukua q sanotaan neliönepäjäännökseksi.

Toisin sanoen neliönjäännös modulo n on luku, jolla on neliöjuuri modulaarisessa aritmetiikassa. Neliönjäännöslause ja Gaussin lemma kertoo hieman lisää neliönjäännösten ja alkulukujen teoriasta. Neliönjäännöksiä käytetään Legendren symbolissa.

Neliönjäännökset ja -epäjäännökset jakaantuvat kahteen osaan. Toisin sanoen jokaiselle alkuluvulle n on olemassa

(n − 1)/2

neliönjäännöstä ja -epäjäännöstä. Se, kumpaan luokkaan tietty luku kuuluu, on varsin sattumanvaraista.

Neliönjäännös modulo n on sellainen luku, jolla on neliöjuuri modulo n. Tätä käsitettä käytetään paljon klassisessa lukuteoriassa.

Neliöjuuren etsiminen modulaariaritmetiikassa, yllä olevan yhtälön ratkaiseminen annetuilla q ja n, on vaikea ongelma. Yleisesti yhdistetylle luvulle n ongelma tiedetään olevan ekvivalentti n:n tekijöihinjaon kanssa. Siten, jos toiseen ongelmaan pystytään kehittämään tehokas ratkaisumenetelmä, samalla pystytään toinenkin ongelma ratkaisemaan tehokkaasti. Toisaalta on NP-täydellinen ongelma selvittää se, onko ongelmalla ratkaisua x<c jollakin annetulla positiivisella kokonaisluvulla c.

Neliönjäännöksillä on keskeinen rooli seuraavissa käsitteissä:

• Legendren symboli
• Neliönjäännöslause
• Gaussin lemma
• Zolotarevin lemma
• Paleyn verkko
• neliönjäännösten jakauma
• neliöiden kongruenssi
• Goldwasser-Micali-salausjärjestelmä

Esimerkkejä

Luku 4 on neliönjäännös modulo 5, koska

${3^{2}}\equiv {4}{\mbox{ (mod }}5{\mbox{)}}.$

Myös luku 1 on neliönjäännös modulo 5:

${4^{2}}\equiv {1}{\mbox{ (mod }}5{\mbox{)}}.$

Sen sijaan luku 3 on epäneliönjäännös modulo 5, koska ei ole olemassa kokonaislukua x, joka toteuttaisi yhtälön

${x^{2}}\equiv {3}{\mbox{ (mod }}5{\mbox{)}}.$

Lähteet

• MathWorld: Quadratic Residue