Primtalsfaktor

En primtalsfaktor av ett positivt heltal är ett primtal som delar talet. Om det positiva heltalet är ett primtal är detta således dess enda primtalsfaktor.

Reella heltal kan delas in i fyra grupper: talet 0, enheterna 1 och -1, primtal och sammansatta tal. Sammansatta tal är en produkt av två eller flera primtal, primtalsfaktorer. Faktoriseringen är entydig, vilket innebär att det endast finns ett sätt, oberoende av ordning, att faktorisera ett sammansatt tal. Denna egenskap hos de hela talen kallas entydig primtalsfaktorisering och dess algebraiska struktur kallas ring med entydig faktorisering eller EF-ring.

Exempel: Talet 6 = 2·3 är alltså delbart med primtalen 2 och 3, varför dessa är primtalsfaktorer till 6. Talet 7 är ett primtal och således primtalsfaktor till sig självt.

Entydig primtalsfaktorisering gäller även för de komplexa tal, vars realdel och imaginärdel är heltal, de så kallade Gaussiska heltalen. Exempel: Talet 5 = (1 + 2i)·(1 - 2i) och består således av två primfaktorer. Talet 7 är primtal även i denna ring varför det endast har en primtalsfaktor det vill säga 7.

Primtalsfaktorisering är en viktig komponent vid dekryptering av krypteringsalgoritmen RSA och hastigheten med vilken primtalsfaktorisering av tal kan göras är ett mått på hur säkert ett sådant system är.