factorisatieproblemen

Factorisatieproblemen zijn wiskundige vragen waarbij een object in factoren moet worden ontleed. In de getallenleer gaat het meestal om het ontleden van een samengesteld getal in priemfactoren, zodat een getal n kan worden geschreven als n = p1^a1 · p2^a2 · ... . Bij polynomen gaat het om het ontleden van een polynoom f(x) over een veld in een product van irreducibele factoren.

Het meest voorkomende soort factorisatieprobleem is het vinden van de priemfactoren van een gegeven samengesteld getal. Sommige getallen kunnen met eenvoudige methoden snel worden ontleed, terwijl voor grote getallen de zoektocht veel rekenkracht vereist. Het verschil in moeilijkheid hangt af van de grootte van n en de structuur van de factoren.

Er bestaan uiteenlopende algoritmen, afhankelijk van het soort object en het gewenste veld. Voor gehele getallen variëren de methoden van eenvoudige trial division tot geavanceerde algoritmen zoals de elliptische-curvemethode (ECM) en de general number field sieve (GNFS), de huidige standaard voor grote getallen. Voor polynomen bestaan er algoritmen om f(x) over velden te factoriseren, zoals Berlekamp's en Cantor-Zassenhaus-methoden; over de rationale getallen wordt vaak gewerkt met modulaire factoren en Hensel-liftings in combinatie met polynoomfactoring.

Factorisatieproblemen zijn van groot belang in de cryptografie: de veiligheid van veel publieke-sleutelalgoritmen (zoals RSA) berust op het veronderstelde moeilijkheidsniveau van het factoriseren van grote integers. Daarnaast vormen ze een centraal onderwerp in de getallenleer en de computeralgebra, en blijven ze een actief onderzoeksgebied met zowel theoretische als praktische toepassingen.