Factorisatie met de algoritmes van Pollard en Lenstra

Abstract

In deze scriptie analyseren we het p−1 factorisatiealgoritme van Pollard en het elliptische kromme factorisatiealgoritme (ECM) van Lenstra. De focus ligt op de getaltheoretische fundamenten van Pollards algoritme, waarbij we de complexiteitsanalyse als secundair beschouwen.

We onderzoeken in detail de keuze van de exponent L in Pollards algoritme. In de literatuur worden hiervoor doorgaans twee opties gebruikt: de faculteit L! of de functie M(L), gedefiniëerd als het product van priemmachten kleiner gelijk L. Door middel van analytische getaltheorie bestuderen we de eigenschappen van L!, terwijl we M(L) analyseren met behulp van de tweede functie van Chebyshev.

Als alternatieve exponent in Pollards algoritme introduceren we een exponent gebaseerd op het product van priemgetallen kleiner dan L. We schatten vanaf de basis de slagingskans van Pollards methode in met deze nieuwe exponent, waarbij we enkele noodzakelijke resultaten over de Möbiusfunctie µ en zijn relatie met de Riemann-zètafunctie behandelen.

Voor Lenstra’s ECM algoritme presenteren we eerst een theoretisch fundament van algebraïsche vlakkrommen, gevolgd door een grondige behandeling van elliptische krommen over Q en over eindige lichamen en hun toepassing in het factorisatiealgoritme.