Change search
ReferencesLink to record
Permanent link

Direct link
The Number Field Sieve
Norwegian University of Science and Technology, Faculty of Information Technology, Mathematics and Electrical Engineering, Department of Mathematical Sciences.
2012 (English)MasteroppgaveStudent thesis
Abstract [en]

We present two algorithms for splitting a general composite number, the quadratic sieve algorithm (QS) and the general number field sieve algorithm (NFS). The former is the method of choice for integers between 50 and 110 digits, and the latter beyond. They share a common strategy, but the NFS is far more sophisticated. We therefore present the QS as a preparation for the NFS. We also give two algorithms for the discrete logarithm problem in prime fields, the index-calculus method (ICM) and the number field sieve for the discrete logarithm problem (NFS-dlog). They have crossover point at 66-digit primes. The only limitation made was restricting to the prime field case. The NFS-dlog uses ideas from both the NFS and the ICM. We also study the algebraic background and estimate the running times of both the NFS and the NFS-dlog.

Place, publisher, year, edition, pages
Institutt for matematiske fag , 2012. , 62 p.
URN: urn:nbn:no:ntnu:diva-20442Local ID: ntnudaim:5811OAI: diva2:610884
Available from: 2013-03-13 Created: 2013-03-13 Last updated: 2013-06-21Bibliographically approved

Open Access in DiVA

fulltext(562 kB)172 downloads
File information
File name FULLTEXT01.pdfFile size 562 kBChecksum SHA-512
Type fulltextMimetype application/pdf
cover(184 kB)43 downloads
File information
File name COVER01.pdfFile size 184 kBChecksum SHA-512
Type coverMimetype application/pdf

By organisation
Department of Mathematical Sciences

Search outside of DiVA

GoogleGoogle Scholar
Total: 172 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Total: 58 hits
ReferencesLink to record
Permanent link

Direct link