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

Master's Thesis from the year 2020 in the subject Mathematics - Applied Mathematics, grade: 14/20, , language: English, abstract: Unraveling the enigma of prime numbers, this groundbreaking work explores the frontiers of integer factorization, a cornerstone of modern cryptography. Delving into the realm where classical algorithms meet quantum computation, the book presents a novel investigation into hybrid methodologies designed to overcome the limitations of traditional approaches. At the heart of this research lies the quest to enhance the efficiency of the Number Field Sieve (NFS), the most powerful classical algorithm for factoring large integers, through the strategic integration of quantum computing techniques. Witness the fusion of number theory and cutting-edge algorithmic optimization as the book meticulously examines the application of quantum annealing, leveraging the capabilities of D-Wave systems, to solve the intricate challenges of factorization. Grasp the complexities of formulating factorization problems within the Ising model and Quadratic Unconstrained Binary Optimization (QUBO) frameworks, navigating the nuances of minor embedding and parameter setting to effectively harness the power of quantum annealers. Furthermore, the book unveils an alternative hybrid strategy, harnessing the potential of quantum SAT solvers to accelerate the critical stages of the Number Field Sieve. Explore the construction of specialized SAT circuits tailored for integer factorization, opening new avenues for leveraging quantum computation in this domain. Through detailed analysis and comparative studies, this book illuminates the strengths and weaknesses of various quantum-classical hybrid methods, offering invaluable insights into the future of integer factorization and its implications for cybersecurity. Discover a comprehensive exploration of techniques, from low-level optimizations to practical implementations, including a detailed case study of factoring the number 35 using D-Wave tools. This book is an essential resource for researchers, cryptographers, and anyone seeking to understand the evolving landscape of integer factorization in the age of quantum computing, revealing how hybrid approaches are paving the way for breakthroughs that could reshape the future of data security by exploring quantum annealing, D-Wave systems, quantum SAT solvers and hybrid algorithms.