Faktorisering

Fra Wikipedia, den frie encyklopædi

I matematikken beskriver begrebet faktorisering en nedbrydning af et udtryk (eksempelvis et tal, et polynomium eller en matrix) til faktorer, der, multipliceret sammen, giver det oprindelige udtryk. Eksempelvis kan tallet 15 primtalsfaktoriseres til tallene 3 og 5, og polynomiet til , som ses at være de to rødder i ligningen, hvilket også let indses ved brug af nulreglen.

Målet med faktorisering er typisk at reducere et udtryk til nogle "grundlæggende byggeklodser"; for eksempel som i ovenstående eksempel; tal til primtal eller polynomier til uforkortelige polynomier. Disse faktoriseringer er beskrevet i henholdsvis Aritmetikkens fundamentalsætning og Algebraens fundamentalsætning.

Primtalsfaktoriseringen af store heltal er i praksis en langvarig proces, da der ikke er nogen kendt metode til hurtig bestemmelse af faktorerne. Denne kompleksitet skaber grundlag for den antagede sikkerhed i asymmetrisk kryptering som f.eks. RSA.