Masterarbeit, 2020
47 Seiten, Note: 14/20
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.
Der GRIN Verlag hat sich seit 1998 auf die Veröffentlichung akademischer eBooks und Bücher spezialisiert. Der GRIN Verlag steht damit als erstes Unternehmen für User Generated Quality Content. Die Verlagsseiten GRIN.com, Hausarbeiten.de und Diplomarbeiten24 bieten für Hochschullehrer, Absolventen und Studenten die ideale Plattform, wissenschaftliche Texte wie Hausarbeiten, Referate, Bachelorarbeiten, Masterarbeiten, Diplomarbeiten, Dissertationen und wissenschaftliche Aufsätze einem breiten Publikum zu präsentieren.
Kostenfreie Veröffentlichung: Hausarbeit, Bachelorarbeit, Diplomarbeit, Dissertation, Masterarbeit, Interpretation oder Referat jetzt veröffentlichen!
Kommentare