Læsetid: 2 min.

Primtal-gåde er løst

Indiske studerende har løst et gammelt matematisk problem med en simpel algoritme
2. september 2002

Matematikere verden over er blevet rystet af to studerendes simple løsning af en oldgammel gåde –bestemmelsen af om et tal er et primtal? Et primtal som 11 eller 19 har den specielle egenskab, at det kun er tallet selv og et, der går op i det. Til trods for denne simple beskrivelse har primtallene drillet og fascineret matematikere i årtusinder.

Euklid viste, at der findes uendeligt mange primtal, og i år 240 før vor tidsregning opfandt Erastosthene en sikker måde at vise, om et tal er et primtal. Desværre opstår der problemer, når tallene bliver meget store (f.eks. over 400 cifre), fordi metoden tidsmæssigt vokser eksponentielt med tallenes størrelse. For meget store tal vil det kræve mere end universets alder at bestemme om de er primtal. Primtal er i dag fundamentet af den udbredte RSA-kryptering, som bla. bruges til hemmeliggørelse og beskyttelse af data ved handel på nettet.

Ligesom nazisternes berømte Enigma kode, som englænderen Alan Turing brød under Anden Verdenskrig, bygger RSA på en ’ubrydelig’ nøgle. En RSA-nøgle skabes ved at tage to kendte primtal f.eks. 11 og 19 og gange dem med hinanden til et tredje pseudoprimtal – 209. For at åbne data-pakken, skal man vide, hvilke to primtal (og der er kun to), der kan danne 209. Det kaldes at faktorisere 209 i dets primtal. Det er ikke så krævende for et lille tal som 209, men med store tal på f.eks. 50 cifre bliver den regnekraft, der kræves, så enorm, at selv computere langt ud i fremtiden ikke vil have nok kraft. Nøglen er derfor stort set ubrydelig.

Kryptering

Den 6. august i år annoncerede de to indiske datalogistuderende Neeraj Kayal og Nitin Saxtena sammen med vejlederen Manindra Agrawal deres løsning på nettet. En lille 13 linjers algoritme, som førende talteoretikere fra hele verden allerede har kommenteret og siger god for. »Det er en smuk løsning, og jeg er glad på deres vegne, men en lille smule flov over jeg ikke selv fandt den,« siger Carl Pomerance fra Lucents Bell Laboratory.

Succesen skyldes en helt ny tilgang til problemet. I stedet for direkte at påvise, at et tal er et primtal, laver de en serie test, der kan afvise, at det er et primtal. Hvis et tal ikke falder i nogen af testene må det være et primtal. »Resultatet er primært af teoretisk interesse,« siger professor i matematik Ian Kiming fra Københavns Universitet.

Han er også imponeret, men praktisk handler det om hastighed, og der er metoden endnu ikke hurtig nok. »De vil måske kunne rafinere deres metode til at generere meget store primtal hurtigt,« siger han, »det vil øge data-sikkerheden, fordi nøglerne bliver nemmere at lave.« Omvendt ville al nutidens datasikkerhed forsvinde som dug for solen, hvis det en dag skulle lykkes at opfinde en metode til at faktorisere et stort tal i dets primtal . Med indernes resultat er forskerne nødt til at overveje om andre simple metoder er blevet overset.

 

Bliv opdateret med nyt om disse emner på mail

Vores abonnenter kalder os kritisk, seriøs og troværdig.
Få ubegrænset adgang med et digitalt abonnement.
Prøv en måned gratis.

Prøv nu

Er du abonnent? Log ind her

Anbefalinger

anbefalede denne artikel

Kommentarer

Euclid-mysteriet,

Er nogle fortællinger om nogle lærerer som sendte nogle af deres elever på tidsrejser, for at de skulle forsøge at bjærge de værker af Euclid, der angiveligt ellers var gået tabt.

Det lykkedes for eleverne at bringe de værker til deres lærerer;
og lærerne fortalte så eleverne, at så skulle alle de værker nu indgå i det obligatoriske pensum.

Alt synes således vellykket "idyl",
men så opdagede lærerne at værkerne igen var
borte,
( borte! - formodentlig som følge af anslag fra nogle helt andre tidsrejsende end førnævnte elever ).

Nic Pedersen

Jeg må med skam erkende, at jeg umiddelbart falder af på den matematiske forståelse, men herfra hatten af for de unge indere, som danskerne jo per automatik påregner at kunne udkonkurrere på viden, tænken og innovation!

Hans Jørgen Lassen

Hr Pedersen skriver:

"som danskerne jo per automatik påregner at kunne udkonkurrere ..."

Gør danskerne det? Hvor har hr. Pedersen dog den tanke fra?

Det er da almindeligt kendt, også her i sognet, at man i Indien har stolte matematiske traditioner.

Men hr. Pedersens nationalmasokisme udkonkurrerer åbenbart hans paratviden på lige dette felt.

Nic Pedersen

@Hans Jørgen Lassen,

jeg tror, at du misforstår mig!
(jeg kan have brugt misforståelig sarkasme!)

Jeg deler til fulde din foragt for den udbredte nationalmasochisme, som du så aldeles rammende kalder det!
Men til gengæld foragter jeg i lige høj grad tanken om Danmark og danskere som et "gudgivent" videnssamfund med deraf automatisk følgende høj løn og levestandard!

Morten Kjeldgaard

"Den 6. august i år annoncerede de to indiske datalogistuderende Neeraj Kayal og Nitin Saxtena sammen med vejlederen Manindra Agrawal deres løsning på nettet."

6. august i år? Yikes, jeg må have sovet i månedsvis.

Michael Kongstad Nielsen

At bestemme primtal ved at finde alle de tal, der ikke er primtal, er det så stor en kunst? Kunne ikke selv de små høns ude i gården gøre det? Om de så er italienere eller indoeuropæere. Hvilket jo er det samme. De kan skelne korn fra sten. Artiklens alder taget i betragtning er det måske forståeligt, at Kim Gram henviser til tidsfaktorens betydning for værkers intakthed.

Nic Pedersen

Jeg skal bestemt ikke gøre mig klog her, men det kræver vel en *Columbus at finde et Columbus-æg, ikke sandt?