The Number Field Sieve
Description
This thesis project is focused on studying the number field sieve. The number field sieve is a factoring algorithm which uses algebraic number theory and is one of the fastest known factoring algorithms today. Factoring large integers into prime factors is an extremely difficult problem, yet also extremely important in cryptography. The security of the cryptosystem RSA is entirely based on the difficulty of factoring certain large integers into a product of two distinct large primes. While the number field sieve is one of the fastest factoring algorithms known, it is still not efficient enough to factor cryptographic sized integers.
In this thesis we will examine the algorithm of the number field sieve and discuss some important advancements. In particular, we will focus on the advancements that have been done in the polynomial selection step, the first main step of the number field sieve. The polynomial selected determines the number field by which computations are carried out in the remainder of the algorithm. Selection of a good polynomial allows for better time efficiency and a higher probability that the algorithm will be successful in factoring.
In this thesis we will examine the algorithm of the number field sieve and discuss some important advancements. In particular, we will focus on the advancements that have been done in the polynomial selection step, the first main step of the number field sieve. The polynomial selected determines the number field by which computations are carried out in the remainder of the algorithm. Selection of a good polynomial allows for better time efficiency and a higher probability that the algorithm will be successful in factoring.
Date Created
The date the item was original created (prior to any relationship with the ASU Digital Repositories.)
2020-05
Agent
- Co-author: Lopez, Rose Eleanor
- Co-author: Lopez, Rose
- Thesis director: Childress, Nancy
- Committee member: Jones, John
- Committee member: Pomerance, Carl
- Contributor (ctb): School of Music
- Contributor (ctb): Department of Physics
- Contributor (ctb): School of Mathematical and Statistical Sciences
- Contributor (ctb): School of Mathematical and Statistical Sciences
- Contributor (ctb): Barrett, The Honors College