Jakolaskun jakojäännöksen laskeminen ja tiedon salaaminen

Matti Heikkinen 3.12.2021

Sisällys

  1. Johdanto
    1. Jakolaskun jakoyhtälö
    2. Kongruenssi
    3. Kongruenttien lukujen jakojäännökset
    4. Kongruenssin tärkeimmät ominaisuudet
  2. Jakojäännöksen selvittäminen ohjelmoimalla
    1. Algoritmi jakojäännöksen selvittämiseksi
    2. Logaritminen algoritmi
    3. Eukleideen algoritmi ja suurin yhteinen tekijä
    4. Diofantoksen yhtälö (lisätietoa)
  3. Shorin kvanttialgoritmi
  4. Tiedon salaaminen ja RSA-Algoritmi

1 Johdanto

Tässä artikkelissa tarkastellaan miten lukujen jaollisuutta ja jakolaskun jakojäännöstä voidaan hyödyntää tiedon salaamisessa. Tiedon salaaminen eli kryptaus ja salatun viestin avaaminen ovat keskeinen osa turvallista ja luotettavaa viestintää yhteiskunnassamme.

Kertaamme lukiomatematiikan lähtökodista mitä tarkoittavat lukuteorian käsitteet jakoyhtälö ja kongruenssi ja miten jakolaskun jakojäännös voidaan selvittää erilaisilla algoritmeilla. Tutustumme python -ohjelmointikielen avulla kahteen algoritmiin, joilla on erilainen tehokkuus ja aikavaatimus. Lisäksi esittelemme lyhyesti miten jaollisuuteen liittyviä ongelmia voidaan tutkia kvanttitietokoneissa suoritettavilla kvanttialgoritmeilla.

Luvussa 1 kerrataan lukiomatematiikasta tutut jakoyhtälön ja kongruenssin käsitteet [1], joita tarvitset luvussa 4, missä käsitellään tiedon salaamiseen ja salatun tiedon avaamisen periaateitta RSA-algoritmin avulla. Luvussa 2 käsitellään erilaisia algoritmeja, joiden avulla voidaan tietokoneilla laskea suurten lukujen jakojäännöksiä,joihin tiedonsalauksessa käytettävät algoritmit perustuvat. Luvussa 3 esitellään lyhyesti Shorin algoritmi[4,5],jota voidaan käyttää kvanttitietokoneissa hyvin suurten lukujen jakolaskun jakojäännösten tutkimiseen. Tiedon salaamisen periaate eli RSA-algoritmi esitellään luvussa 4.

Jypyter – notebook tiedosto on ladattavissa Otaniemen lukion GitHub-tililtä https://github.com/otaniemenlukio/lukiomatematiikkaa-ohjelmoimalla

Jos haluat suorittaa tai muokata koodiesimerkkejä, lataa tiedosto yllä olevasta linkistä Otaniemen lukion GitHub-sivuilta.

HUOMAA: Teoria ja python-esimerkit käännetty html-versioksi, jotta materiaalin voi lukea helposti nettiselaimessa.

Linkki materiaaliin: