Factorization of binary polynomials

Abstract

This thesis describes a solution to a cryptographic programming challenge originally posted by Nintendo in order to gain job applicants. The encryption method turned out to be the same as binary polynomial multiplication which means decryption can be done with binary polynomial factorization. While providing shallow exploration of other options, the main approach in this thesis was to first compute square-free factorization of a polynomial using David Yun's algorithm from 1974 and then to apply slower Elwyn Berlekamp's algorithm on those square-free factors to compute a proper irreducible factorization of the polynomial. In addition to just explaining and implementing algorithms, the details of how to make these computations fast on a computer system have been explained in detail. The binary polynomial factorization translates really efficiently to a computer algorithm where one bit represents one coefficient. Using this fact allowed author of this thesis to efficiently implement the algorithms to solved the challenge as the 273rd person since the it was posted on-line.

Tässä työssä kuvataan ratkaisu erääseen kryptografiseen ongelmaan, jonka peliyhtiö Nintendo julkaisi tavoitteenaan tarjota työmahdollisuus ongelman ratkaisseille. Lähemmässä tarkastelussa selvisi, että heidän salausalgoritminsa keskiössä oli binääripolynomien kertolasku ja siten purkualgoritmi sekä ongelman ratkaisu vaativat binääripolynomien tekijöihin jakoa. Itse ratkaisu koostuu kahdesta vaiheesta. Ensin binääripolynomi jaetaan neliöttömiin tekijöihin käyttäen David Yunin algoritmia vuodelta 1974. Tämän jälkeen neliöttömät tekijät jaetaan alkupolynomeihin käyttäen hieman hitaampaa Elwyn Berlekampin algoritmia. Molemmat algoritmit toteutetaan C++ kielellä modernilla tietokoneella ja tuon toteutuksen tehokkuuteen kiinnitettään työssä erityistä huomiota. Näiden kahden algoritmin kuvaamisen lisäksi työssä esitellään pintapuolisesti muita tapoja jakaa polynomi tekijöihin äärellisen kentän yli tarkoituksena antaa kuva siitä, kuinka alan tutkimus on kehittynyt. Binääripolynomit on hyvin tehokasta esittää tietokoneella niin, että yksi bitti vastaa yhtä kerrointa. Tätä hyväksikäyttäen työssä saatiin aikaiseksi tehokas toteutus, jolla päästiin 273ksi tehtävän suorittaneeksi.