Kompleksiteten til noen kryptologisk viktige algoritmer

Abstract

Denne hovedfagsoppgaven har som mål å sammenligne teoretisk og praktisk kompleksitet til algoritmer som har stor kryptologisk betydning. Et av målene er å avsløre den skjulte konstanten bak O-notasjonen, slik at algoritmene kan sammenlignes på et reelt grunnlag. I tillegg er det sett på sammenheng mellom sikkerhet, størrelsen på tall, asymptotisk og praktisk kompleksitet. Spesielt algoritmer som inngår i kryptering / dekryptering er forsøkt analysert i dybden. Algoritmer som er av mindre betydning er kun analysert med tanke på den asymptotiske kompleksiteten, mens andre algoritmer kun er beskrevet. De viktigste algoritmene er programmert i C, og kjørt på en datamaskin for å bedre kunne sammenligne dem. Spesielt gjelder det multiplikasjon, der 7-8 algoritmer er analysert og 3 av dem programmert. Programmering av langtallsaritmetikk er forøvrig noe av det som har krevd mest tid. Totalt gir oppgaven gir en brukbar oversikt over mer enn 30 tallteoretiske algoritmer som har betydning innen moderne kryptologi.