Johdatus neliönjäännöksiin

Abstract

Tässä tutkielmassa perehdytään neliönjäännöksiin ja joihinkin niihin liittyviin sovelluksiin. Tutkielmassa käydään läpi neliönjäännösten perusteisiin liittyviä määritelmiä ja lauseita esimerkkien kera. Aluksi tarkastellaan yleistä toisen asteen kongruenssia ja sen ratkeavuutta, joka johdattelee tutkimaan neliönjäännöksiä ja epäneliönjäännöksiä. Osoitamme myös, että tällä kongruenssilla on joko kaksi ratkaisua, tai ei yhtään ratkaisua. Eulerin kriteerin, Legendren symbolin ja Gaussin lemman kautta päästään tutustumaan erääseen matematiikan merkittävimmistä ja eleganteimmista tuloksista, resiprookkilakiin. Lukijan oletetaan hallitsevan lukuteorian ja erityisesti kongruensseilla laskemisen perusteet.

Loppuosassa tutustutaan neljään neliönjännöksiin liittyvään sovellukseen. Ensimmäiseksi tarkastellaan graafiteorian erästä haaraa, jossa neliönjäännösten avulla konstruoidaan tietyn ominaisuuden omaavia turnauksia. Seuraavaksi näytetään miten neliönjäännöksiä voidaan käyttää tiettyjä kertalukuja olevien Hadamardin matriisien konstruointiin. Kolmanneksi esitellään Eulerin pseudoalkuluvut. Tutkielman päätteeksi tutustutaan nollatietotodistuksiin. Tämä tärkeä neliönjäännösten sovellus on käyttökelpoinen esimerkiksi identiteettivarmennuksissa tietoverkoissa, sekä korttivarmennuksissa kortin ja päätteen välillä.