Izbrane teme sodobne fizike in matematike

Shorov algoritem

Shorov algoritem je kvantni algoritem za faktorizacijo števil. Članek začne s šifriranjem RSA, ki ga je mogoče razbiti s Shorovim algoritmom, kar služi kot motivacija za nadaljno obravnavo. Sledi predstavitev teoretičnega ozadja algoritma, vključno z osnovami kvantnih vezij, kvantno Fourierovo transformacijo in oceno faze. Ti koncepti so nato združeni v celovit opis delovanja Shorovega algoritma, njegova uporaba pa je ponazorjena s faktorizacijo števila 15.

Shor’s algorithm

Shor’s algorithm is a quantum algorithm for integer factorization. As a motivating example, this article presents RSA encryption, which is known to be breakable using the Shor’s algorithm. Then it introduces the necessary theoretical background, including the basics of quantum circuits, the Quantum Fourier Transform and phase estimation. These concepts are then combined into a complete explanation of Shor’s Algorithm, which is applied to factorize the number 15.

avtor: Luka Papež
številka: 2
letnik: 12

PDF (0.5 Mb)

Vsi članki iz te številke

© 2025 Fakulteta za matematiko in fiziko Univerze v Ljubljani

Članke, objavljene pred septembrom 2025, lahko obiskovalci berejo, brskajo in/ali prenesejo za osebno in nekomercialno uporabo. Te vsebine je prepovedano reproducirati, spreminjati, prilagajati, objavljati ali prodajati brez pisnega soglasja avtorja članka in nosilca avtorskih pravic v citatu. Članki, objavljeni septembra 2025 in kasneje, so objavljeni pod licenco CC BY 4.0 oziroma izjemoma CC BY SA 4.0. Informacije o licenci so navedene v člankih.

For articles published before September 2025, readers may view, browse, and/or download material for temporary copying purposes only, provided these uses are for noncommercial personal purposes. That material may not be further reproduced, distributed, modified, adapted, published, or sold in whole or part, without prior written permission frm the author and copyright owner as cited. Articles published in September 2025 and later are instead provided under the terms of the CC BY 4.0 or CC BY SA 4.0 licenses. License information is available in each article.