Original title:
Testování prvočíselnosti v polynomiálním čase
Translated title:
Polynomial time primality testing
Authors:
Bednaříková, Alžběta ; Žemlička, Jan (advisor) ; Čech, Martin (referee) Document type: Bachelor's theses
Year:
2020
Language:
cze Abstract:
[cze][eng] Tématem práce je testování prvočíselnosti v polynomiálním čase. Text se zaměřuje na konkrétní algoritmus, který v roce 2002 publikovali Manindra Agrawal, Neeraj Kayal a Nitin Saxena a je znám jako AKS test prvočíselnosti. V úvodu této práce jsou zopakovány důležité vlastnosti a pojmy nezbytné k porozumění textu. Poté je vysvětlena základní idea testu, pokračuje se popsáním samotného algoritmu. Cílem práce je dokázání Věty o správnosti AKS testu z postupně vybudované teorie a výpočet časové složitosti algoritmu. Na závěr je dokázáno, že vypočtená časová složitost je polynomiální.The topic of my thesis is the testing of prime numbers in polynomial time. The text focuses on the specific algorithm published in 2002 by Manindra Agrawal, Neeraj Kayal and Nitin Saxena and it is known as the AKS primality test. In the introduction of this work, important properties and concepts essential for the text understanding are revised. Then the basic idea of the test is explained. The description of the algorithm itself continues. The aim of the work is to prove the Theorem on the correctness of the AKS test from a gradually built-up theory and to calculate the time complexity of the algorithm. Finally, it is proved that the calculated time complexity is polynomial.
Keywords:
AKS algorithm; prime numbers; time complexity; AKS algoritmus; prvočísla; časová složitost
Institution: Charles University Faculties (theses)
(web)
Document availability information: Available in the Charles University Digital Repository. Original record: http://hdl.handle.net/20.500.11956/121626