Kwadratische zeef

De kwadratische zeef is een algoritme om samengestelde getallen te ontbinden in priemfactoren. Deze methode is gebaseerd op Dixons factorisatiemethode en is in 1984 ontwikkeld door de Amerikaanse wiskundige Carl Pomerance. De kwadratische zeef is in 1994 gebruikt om RSA-129 te kraken. Het is een van de snelste algoritmen om een getal in factoren te ontbinden. De getallenlichamenzeef is een stuk ingewikkelder dan de kwadratische zeef, maar sneller voor getallen groter dan 130 cijfers. De tijd die de kwadratische zeef en de getallenlichamenzeef nodig hebben om getallen tussen de 100 en 130 cijfers te ontbinden, is sterk afhankelijk van de implementatie van het algoritme en de beschikbare opslagruimte. Pomerance schrijft dat de kwadratische zeef sneller is voor getallen tot 100 cijfers.^[1]

1. ↑ C Pomerance, A tale of two sieves, Notices of the American Mathematical Society. 43 (1996), 1473-1485.