Factoring large numbers and computing discrete logarithms are presumed to be hard problems. No polynomial time solution for those problem has yet been found. Those problems have many significant applications, particularly in cryptography. Several cryptosystems base their security on their supposed difficulty. In this thesis we present some of the algorithms to solve these two problems. We mainly explore sieving as a tool for that purpose. Among other material we describe the Quadratic Sieve and the Number Field Sieve as they apply to factoring. We finally sketch how the Number Field Sieve can be applied to compute discrete logarithms.
展开▼
