Algoritmy pro řešení soustav lineárních rovnic s řídkou maticí
| Thesis title in Czech: | Algoritmy pro řešení soustav lineárních rovnic s řídkou maticí |
|---|---|
| Thesis title in English: | Algorithms for finding solutions of linear systems with sparse matrices |
| Academic year of topic announcement: | 2018/2019 |
| Thesis type: | diploma thesis |
| Thesis language: | |
| Department: | Department of Algebra (32-KA) |
| Supervisor: | doc. Mgr. Pavel Příhoda, Ph.D. |
| Author: | hidden - assigned and confirmed by the Study Dept. |
| Date of registration: | 11.08.2018 |
| Date of assignment: | 30.08.2018 |
| Confirmed by Study dept. on: | 20.12.2018 |
| Guidelines |
| Práce by měla podat přehled základních metod využívaných v lineární fázi faktorizačních algoritmů, případně algoritmů pro výpočet diskrétního logaritmu metodou index calculus, a jejich modifikací. Zkoumat se budou zejména metody vycházející z Lanczosova a Wiedemannova algoritmu. Jedním z cílů práce by mělo být porovnání jednotlivých metod z hlediska efektivity při nasazení v konkrétních aplikacích. |
| References |
| Don Coppersmith: Solving Homogeneous Linear Equations Over GF(2) via Block Wiedemann Algorithm, Mathematics of Computation 62(1994), pp. 333-350.
Peter L. Montgomery: A Block Lanczos Algorithm for Finding Dependecies over GF(2), in Advances in Cryptology - EUROCRYPT'95, LNCS 921, pp. 106-120. Michael Peterson, Chris Monico: F_2 Lanczos revisited, Linear Algebra and its Applications 428 (2008), pp. 1135 - 1150. Jeremy Teitelbaum: Euclid's algorithm and the Lanczos method over finite fields, Mathematics of Computation 67 (1998), pp. 1665 - 1678. |