kokonaislukualgoritmit

Kokonaislukualgoritmit ovat algoritmeja, jotka käsittelevät kokonaislukuja tai suorittavat operaatioita, joiden tulokset ovat kokonaislukuja. Niitä tarvitaan sekä teoreettisessa numeerisessa laskennassa että käytännön sovelluksissa, kuten kryptografiassa ja suurten lukujen laskennassa. Niiden tavoitteena on tarjota tarkkoja tuloksia ja tehokasta suorituskykyä suurella syötteellä.

Yleisiä tehtäviä ovat gcd:n (yhteinen jakaja) laskeminen, inversien määrittäminen modulo m sekä modulaarinen laskenta. Näihin liittyy usein tehokkaita toteutuksia, kuten Euklidin algoritmi ja sen laajennettu versio sekä exponentiation by squaring -menetelmä. Primaliteettitestit, kuten Miller-Rabin ja AKS, sekä faktorisointimenetelmät, kuten Pollardin rho ja ECM, kuuluvat keskeisiin kokonaislukualgoritmeihin. Suurten lukujen käsittelyyn käytetään myös nopeita kokonaislukujen kertolasku- ja potenssialgoritmeja, kuten Karatsuban, Toom-Cookin ja Schönhage–Strassenin menetelmiä.

Käytännön sovelluksia ovat kryptografia, erityisesti RSA- ja elliptic curve -perusteiset järjestelmät, digitaalisten allekirjoitusten sekä salausmekanismien toteuttaminen sekä teoreettinen lukuteoria. Kompleksisuushinnoissa gcd:n laskeminen on erittäin nopeaa (noin O(log min(a,b))), kun taas primaliteetti- ja faktorisointimenetelmien tehokkuus riippuu käyttötavasta; AKS on deterministinen polylogaritminen testi, Miller-Rabin taas on probabilistinen testi.