Original title:
Shorův algoritmus v kvantové kryptografii
Translated title:
Shor's algorithm in Quantum Cryptography
Authors:
Nwaokocha, Martyns ; Vašík, Petr (referee) ; Hrdina, Jaroslav (advisor) Document type: Master’s theses
Year:
2021
Language:
eng Publisher:
Vysoké učení technické v Brně. Fakulta strojního inženýrství Abstract:
[eng][cze]
Kryptografie je velmi důležitým aspektem našeho každodenního života, protože poskytuje teoretický základ informační bezpečnosti. Kvantové výpočty a informace se také stávají velmi důležitou oblastí vědy kvůli mnoha aplikačním oblastem včetně kryptologie a konkrétněji v kryptografii veřejných klíčů. Obtížnost čísel do hlavních faktorů je základem některých důležitých veřejných kryptosystémů, jejichž klíčem je kryptosystém RSA . Shorův kvantový faktoringový al-goritmus využívá zejména kvantový interferenční účinek kvantového výpočtu k faktorovým semi-prime číslům v polynomiálním čase na kvantovém počítači. Ačkoli kapacita současných kvantových počítačů vykonávat Shorův algoritmus je velmi omezená, existuje mnoho rozsáhlých základních vědeckých výzkumů o různých technikách optimalizace algoritmu, pokud jde o faktory, jako je počet qubitů, hloubka obvodu a počet bran. v této práci jsou diskutovány, analyzovány a porovnávány různé varianty Shorova factoringového algoritmu a kvantových obvodů. Některé varianty Shorova algoritmu jsou také simulované a skutečně prováděné na simulátorech a kvantových počítačích na platformě IBM QuantumExperience. Výsledky simulace jsou porovnávány z hlediska jejich složitosti a míry úspěšnosti. Organizace práce je následující: Kapitola 1 pojednává o některých klíčových historických výsledcích kvantové kryptografie, uvádí problém diskutovaný v této práci a představuje cíle, kterých má být dosaženo. Kapitola 2 shrnuje matematické základy kvantového výpočtu a kryptografie veřejných klíčů a popisuje notaci použitou v celé práci. To také vysvětluje, jak lze k rozbití kryptosystému RSA použít realizovatelný algoritmus pro vyhledávání objednávek nebo factoring. Kapitola 3 představuje stavební kameny Shorova algoritmu, včetně kvantové Fourierovy transformace, kvantového odhadu fází, modulární exponentiace a Shorova algoritmu. Zde jsou také uvedeny a porovnány různé varianty optimalizace kvantových obvodů. Kapitola 4 představuje výsledky simulací různých verzí Shorova algoritmu. V kapitole 5 pojednejte o dosažení cílů disertační práce, shrňte výsledky výzkumu a nastíňte budoucí směry výzkumu.
Cryptography is a very important aspect of our daily lives as it gives the theoretical foun-dation of information security. Quantum computation and information is also becoming avery important field of science because of its many application areas including cryptologyand more specifically in public key cryptography.The difficulty of numbers into its prime factors is the basis of some important publickey cryptosystems key of which is the RSA cryptosystem. Shor’s Quantum factoring al-gorithm leverages most especially the quantum interference effect of quantum computingto factor semi-prime numbers in polynomial time on a quantum computer. Though thecapacity of current quantum computers to execute the Shor’s Algorithm is very limited,there are many extensive foundational scientific research on various techniques of opti-mizing the algorithm in terms of factors such as number of qubits, depth of the circuitand number of gates.In this thesis, various variants of the Shor’s factoring algorithm and quantum circuits arediscussed, analysed and compared. Also, some variants of the Shor’s algorithm are simu-lated and actually executed on simulators and quantum computers in the IBM QuantumExperience platform. The simulation results are compared in terms of their complexityand success rate.The organization of the thesis is as follow: Chapter 1 discusses some key historical resultin quantum cryptography, states the problem discussed in this thesis and presents the ob-jectives to be achieved. Chapter 2 summarizes the mathematical background in quantumcomputing and public key cryptography as well as describing the notation used through-out the thesis. This also explains how a realizable order-finding or factoring algorithmcan be used to break the RSA cryptosystem. Chapter 3 presents the building blocks ofShor’s algorithm including the Quantum Fourier Transform, Quantum Phase Estimation,Modular Exponentiation and Shor’s algorithm in detail. Different optimization variantsof the quantum circuits are also presented and compared here. Chapter 4 presents theresults of the simulations of the various versions of the Shor’s algorithm. In Chapter 5, wediscuss the achievement of thesis goals, summarize the results of the research and outlinepossible future research directions.
Keywords:
Faktorizace; Fourierova trans-formace; Kryptografie; Kvantové algoritmy; Kvantové počítání; RSA; Shorův algoritmus; Cryptography; Factorization; Fourier trans-formation; Quantum Algorithm; Quantum Computing; RSA; Shor Algorithm
Institution: Brno University of Technology
(web)
Document availability information: Fulltext is available in the Brno University of Technology Digital Library. Original record: http://hdl.handle.net/11012/200081
guest ::
