Dansker skaber verdens mest tilfældige forsknings-resultat

Tilfældighed er for en computerprogrammør, hvad en køkkenkniv er for en kok og en skruetrækker for en tømrer: Et uundværligt værktøj man bruger hele tiden, til alt. Der skal tilfældige funktioner til for at få vores Google-søgninger og smartphones og computerprogrammer til at virke. Og jo mere tilfældige funktionerne er, des bedre.

Den danske forsker Mikkel Thorup har nu skabt verdens mest tilfældige funktion.

»Jeg har fundet den allermest tilfældige funktion, som det på nuværende tidspunkt er realistisk at implementere,« siger Mikkel Thorup, der er professor på Datalogisk Institut på Københavns Universitet.

På IT-Universitetet i København mener professor Rasmus Pagh, der forsker i algoritmer, at Mikkel Thorups funktion – en såkaldt hash-funktion – er banebrydende.

»Det er verdens bedste funktion i en masse tilfælde. Lidt ligesom, at der ikke er en skruetrækker, der passer til alle skruer, så er det heller ikke sikkert, den vil være det bedste til alt. Men den her funktion vil være den bedste til vældigt mange skruer,« siger Rasmus Pagh, som mener, at Mikkel Thorups funktion har stort potentiale.

»Hash-funktioner bliver brugt i næsten al software. Det er noget, alle programmører lærer om som noget af det første, når man lærer om at skabe effektiv software. Det er noget, der kan bruges til vældigt mange ting,« siger Rasmus Pagh.

Kan finde data hurtigt

Mikkel Thorup vendte i 2013 hjem fra mange års forskning i USA for at bringe sin forskning i computeralgoritmer til Danmark som topforsker i Det Frie Forskningsråds Sapere Aude-program med en kæmpebevilling på 10,5 millioner kroner.

Verdens mest tilfældige funktion er første resultat i forskningsprojektet, der startede i oktober.

De tilfældige hash-funktioner bruges blandt andet til lynhurtigt at finde frem til information. Ligesom vi placerer ting i forskellige rum i vores hus – bøger i reolen i stuen, tandbørster på badeværelset – fordeler funktionerne data, der skal gemmes i computerens hukommelse, på en måde så det kan findes hurtigt igen.

»Du kan næsten ikke gøre noget med en computer uden at bruge tilfældighed,« siger Mikkel Thorup. Hvis det hele blev gemt samme sted, ville det tage meget lang tid at finde ens data igen, ligesom det ville tage meget lang tid at finde bogen, man lånte af Tante Olga, hvis alle ens ejendele var stablet oven på hinanden og proppet ind i husets pulterkammer. Fordelen ved hash-funktionerne er, at data bliver jævnt fordelt mellem rummene, når de bliver tilfældigt placeret.

Kan ikke være helt tilfældige

Men helt tilfældigt kan det ikke være, understreger Mikkel Thorup, for så kan man ikke finde sine ting igen. Man kan ikke bare slå en terning og afgøre, at sofaen ender i bryggerset. Tricket er nemlig, at hash-funktionen foretager den samme udregning, når tingen skal placeres – og når man skal finde den igen.

Ved at se på resultatet af udregningen, ved computeren præcis hvilket rum, den skal lede i, og fordi den tilfældige funktion har fordelt tingene jævnt, så der ikke er ret mange ting i hvert rum, er det hurtigt at finde, forklarer Mikkel Thorup.

»Det med at gemme ting er den anvendelse af hash-funktioner, der er nemmest at forstå. Men det, der gør hash-funktioner sjove, er al den magi, man kan med dem,« siger Mikkel Thorup og forklarer, at funktionerne også er afgørende for at kunne udregne statistik, for at få kryptering til at fungere, for at gøre programmer i stand til selv at lære fra data – såkaldt machine learning, en del af skabelsen af kunstig intelligens – og for beregninger på big data, altså meget, meget store datasæt.

Mikkel Thorup bliver midt i forklaringen stille i den anden ende af telefonen. Han leder efter en videnskabelig artikel, der forklarer hash-funktioner, men han kan ikke huske, hvor på computeren han har gemt den.

»Jeg ville virkelig ønske, jeg havde en hash-funktion i hovedet, for den tid, jeg bruger på at lede, er helt uacceptabel,« siger han. »Det, jeg har kaldt artiklen, er ikke lavet af en matematisk funktion, så jeg kan ikke genberegne funktionen for at finde ud af, hvad den hedder lynhurtigt. I stedet skal jeg gætte, hvad jeg har kaldt den.«

Virker ikke altid

Udfordringen er altså at skabe en funktion, der på én gang altid vil placere samme ting samme sted – men samtidig fordeler tingene tilfældigt. Det er derfor, man kan tale om mere eller mindre tilfældige funktioner – hvor Mikkel Thorup altså har skabt den, der giver størst sikkerhed for et tilfældigt resultat.

Mikkel Thorup illustrerer problemet med mindre tilfældige funktioner med volleyball. Hvis man sætter en computer til at fordele en gruppe spillere i to hold, kunne det gøres med en hash-funktion, der placerer alle, der er født på en lige dato på det ene hold og alle, der er født på en ulige dato på det andet.

Så længe man sørger for at oplyse fødselsdatoer til funktionen, bliver spillerne altså fordelt jævnt på de to hold – og man kan altid lynhurtigt finde ud af, hvilket hold en spiller er placeret på ved at kigge på fødselsdatoen.

»Problemet opstår, hvis man i stedet kommer til at give personnumre til funktionen, der skelner mellem lige og ulige. Så får du pludselig delt holdene i drengene mod pigerne og så er det ikke tilfældigt alligevel,« siger Mikkel Thorup.

Alvorlige sikkerhedsproblemer

Funktioner, som programmørerne troede, var tilfældige, men som i specifikke tilfælde viste sig ikke at være det, har i nogle tilfælde skabt alvorlige sikkerhedsproblemer. Når kriminelle har kunnet forudsige sikkerhedssystemer, der ellers skulle være tilfældige, har de kunnet bryde krypteringer og ind i netbanker.

»For at tage et eksempel, som min mor er glad for: Hvis jeg skal lave en telefonbog, kan en god funktion sortere efter bogstaver i efternavnet. Men hvis jeg skal lave en telefonbog for min egen familie, ender alle under Thorup. Så fik jeg slet ikke spredt tingene ud,« siger Mikkel Thorup.

Når den slags situationer opstår, hvor for meget data ender samme sted, kan det få et computersystem til at bryde sammen.

»Det kan være alvorligt, hvis det for eksempel er i en autopilot i en flyvemaskine, hvor der pludselig sker det, der ikke må ske. Der skal man gerne være så sikker på sin funktion, at man kan lægge hovedet på blokken og sige, at hvis funktionen ikke holder, så må du hugge det af,« siger Mikkel Thorup.

Kræver stor computerkraft

Problemet er ifølge Mikkel Thorup, at mange programmører ikke er klar over, at den slags situationer kan opstå. Funktionerne ser nemlig ofte ud til at virke i praksis, selvom der ikke er matematisk bevis for, at de gør.

Den her funktion vil være den bedste til vældigt mange skruer.

Professor Rasmus Pagh, IT-Universitetet i København

Her kommer Mikkel Thorups nye tilfældige funktion ind i billedet, for hans tilgang er at skabe de matematiske beviser, så man er sikker på, at funktionerne virker.

»Selv de professionelle gør det tit amatøragtigt, fordi teorien ikke er på plads,« siger Mikkel Thorup.

Funktionen er inspireret af en funktion, der var i skakcomputere i 1970'erne, men som ingen rigtigt interesserede sig for – før Mikkel Thorup sammen med en rumænsk kollega viste potentialet i den. De seneste år har Mikkel Thorup videreudviklet funktionen til at være den mest tilfældige funktion hidtil.

»Det er en tung funktion, der kræver rigtigt meget computerkraft. Den kan bruges, når man har brug for rigtig meget tilfældighed, men det koster hastighed at bruge den. Så det er meget spændende, om jeg kan finde noget, der bruger mindre computerkraft. Men det er den første funktion nogensinde, der overhovedet er realistisk at implementere,« siger Mikkel Thorup.

Stor del af verdens beregninger

Ambitionen er nu at skabe endnu bedre metoder til at skabe tilfældige resultater af hash-funktioner.

»Jeg vil gerne kunne finde ud af at tildele helt tilfældige tal til ting. Sådan at hvis du har en mængde af ting, så har alle ting i mængden præcis samme sandsynlighed for at få det mindste tal. Det er der på nuværende tidspunkt ikke nogen, der kan finde ud af, men hvis jeg kan finde ud af det, så er der en hel masse ting, som vil kunne lade sig gøre. Ting, som man ikke kan nu,« siger Mikkel Thorup.

»Da tilfældighed bruges overalt, betyder det, at det er en stor del af al beregning i verden, jeg prøver at levere grundlaget for. Det er selvsagt et program, der aldrig vil blive afsluttet,« siger Mikkel Thorup.