Testování prvočíselnosti v polynomiálním čase
Thesis title in Czech: | Testování prvočíselnosti v polynomiálním čase |
---|---|
Thesis title in English: | Polynomial time primality testing |
Key words: | AKS algoritmus, prvočísla, časová složitost |
English key words: | AKS algorithm, prime numbers, time complexity |
Academic year of topic announcement: | 2019/2020 |
Thesis type: | Bachelor's thesis |
Thesis language: | čeština |
Department: | Department of Algebra (32-KA) |
Supervisor: | doc. Mgr. et Mgr. Jan Žemlička, Ph.D. |
Author: | hidden![]() |
Date of registration: | 27.07.2019 |
Date of assignment: | 17.10.2019 |
Confirmed by Study dept. on: | 21.11.2019 |
Date and time of defence: | 22.09.2020 09:00 |
Date of electronic submission: | 28.07.2020 |
Date of submission of printed version: | 28.07.2020 |
Date of proceeded defence: | 22.09.2020 |
Opponents: | Mgr. Martin Čech, Ph.D. |
Guidelines |
Cílem práce bude kompletní matematický popis deterministického algoritmu s polynomiální časovou složitostí testujícího prvočíselnost, který roku 2002 zveřejnili Manindra Agrawal, Neeraj Kayal a Nitin Saxena [1]. Kromě původního AKS testu se student může zabývat rovněž jeho variantou [2] nebo na příkladech výpočtů ilustrovat meze jeho praktického použití. |
References |
[1] Agrawal, M., Kayal, N., Saxena, N.: PRIMES is in P. Annals of Mathematics, 160 (2004), 781–793.
[2] Bernstein, D.J: Proving Primality in Essentially Quartic Random Time, Mathematics of Computation Vol. 76, No. 257 (Jan., 2007), 389-403. [3] Dietzfelbinger, M.: Primality testing in polynomial time. From randomized algorithms to “PRIMES is in P”. Lecture Notes in Computer Science 3000, Springer Berlin 2004. |