Hybrid Number Field Sieve (NFS): Classical and Quantum approaches

Master's Thesis, 2020

47 Pages, Grade: 14/20

Abstract or Introduction

The Number Field Sieve (NFS) is currently the best integer factoring algorithm for general RSA moduli on classical computers. While we know that Shor’s quantum algorithm solves the problem in quantum polynomial-time, the size of the fault-tolerant quantum computers needed for its concrete application seems currently beyond reach for the next decades. There are several bottlenecks in the NFS algorithm which are almost “combinatorial in nature” (for example the core of the sieving part). Several approaches have been proposed in order to mix quantum computing and classical computing for NFS. Among them, the work of Bernstein, Biasse and Mosca, implementing the quantum Grover’s search algorithm as a subroutine of classical NFS and more recently the work of Mosca et al. using speedup with a quantum SAT solver (and not requiring a fault-tolerant quantum computer). On the other hand, Jiang, Britt, Humble and Kais present an alternative way to solve the factorization problem using quantum annealers, a method which has a simplistic formalism and which uses laws of physics to express the factorization problem as an executable Ising model. In this work we have implemented a factorization example using quantum annealing formalism and the D-Wave annealing tools by introducing variable simplifications in order to reduce the number of qubits needed to perform the factorization. We compare at the low-level, combining number theory, quantum computing and algorithmic optimizations the aforementioned approaches.


Hybrid Number Field Sieve (NFS): Classical and Quantum approaches
Catalog Number
ISBN (eBook)
hybrid, number, field, sieve, classical, quantum
Quote paper
Rina Ismailati (Author), 2020, Hybrid Number Field Sieve (NFS): Classical and Quantum approaches, Munich, GRIN Verlag, https://www.grin.com/document/974015


  • No comments yet.
Read the ebook
Title: Hybrid Number Field Sieve (NFS): Classical and Quantum approaches

Upload papers

Your term paper / thesis:

- Publication as eBook and book
- High royalties for the sales
- Completely free - with ISBN
- It only takes five minutes
- Every paper finds readers

Publish now - it's free