Testování prvočíselnosti
| Thesis title in Czech: | Testování prvočíselnosti |
|---|---|
| Thesis title in English: | Primality testing |
| Academic year of topic announcement: | 2006/2007 |
| Thesis type: | Bachelor's thesis |
| Thesis language: | |
| Department: | Department of Applied Mathematics (32-KAM) |
| Supervisor: | doc. RNDr. Martin Klazar, Dr. |
| Author: | hidden - assigned and confirmed by the Study Dept. |
| Date of registration: | 18.10.2006 |
| Date of assignment: | 18.10.2006 |
| Guidelines |
| Student vypracuje přehled algoritmů pro testování a dokazování prvočíselnosti, zejména tzv. AKS testu, s důrazem na
matematické teorémy, o něž se tyto algoritmy opírají. Podá též přehled jejich časové složitosti a pokusí se zlepšit složitost AKS testu. |
| References |
| [1] M. Agrawal, N. Kayal and N. Saxena, PRIMES is in P, Ann. of Math. (2) 160 (2004) 781-793.
[2] R. Crandall and C. Pomerance, Prime Numbers. A Computational Perspective. Second Edition, Springer, Berlin, 2006. [3] L. Kučera, Kombinatorické algoritmy, SNTL, Praha, 1983. Popř. další časopisecká literatura. |
| Preliminary scope of work |
| Student vypracuje přehled algoritmů pro testování a dokazování prvočíselnosti, zejména tzv. AKS testu, s důrazem na matematické teorémy, o něž se tyto algoritmy opírají. Podá též přehled jejich výpočetní složitosti a pokusí se zlepšit složitost AKS testu. |
| Preliminary scope of work in English |
| The task of the student is to produce a survey of algorithms for primality testing and primality proving, including the AKS test,
with emphasize on the underlying mathematics. Also, (s)he will survey computational complexity of these algorithms and will attempt to improve the computational complexity of the AKS test. |