| Computational algebra and number theory |
ter |
|||||
| Teaching Staff in Charge |
| Prof. MARCUS Andrei, Ph.D., marcus@math.ubbcluj.ro |
| Aims |
|
We present several fundamental algorithms with applications to number theory. We discuss the complexity of these algorithms.The main stress will be on primality tests and factorization of integers. |
| Content |
|
1. Notiuni de complexitatea algoritmilor. Notatia O, clase de complexitate.
2. Congruente si clase de resturi. Algoritmul lui Euclid, functia lui Euler, teorema chineza a restului, resturi patratice, simbolul lui Legendre. 3. Teste de primalitate. Testele de primalitate Fermat, Solovay-Strassen si Miller-Rabin, teste deterministice. 4. Metode de factorizare. Metode elementare, metoda Rho, metoda bazei de factori, metoda fractiilor continue, metoda sitei patratice. Aplicatii in criptografie. 5. Polinoame peste corpuri finite. Corpuri finite, logaritm discret, polinoame ireductibile, algoritmul lui Berlekamp de factorizare a polinoamelor. Aplicatii in criptografie 6. Alti algoritmi. Adunare rapida, transformarea Fourier rapida. |
| References |
|
1. N. Koblitz - A Course in Number Theory and Cryptography, Springer-Verlag 1994
2. K. Ireland, M. Rosen - A Classical Introduction to Number Theory, Springer-Verlag 1990 3. D. Bressoud, S. Wagon - A Course in Computational Number Theory, Springer-Verlag 2000 4. D. Knuth - A számítógép programozás müvészete, Müszaki Könyvkiadó, Budapest 5. T. H. Cormen, Ch. Leiserson, R. R. Rivest - Algoritmusok, Müszaki könyvkiadó, Budapest 6. M. Schönert et al, GAP - Groups, Algorithms and Programming, RWTH Aachen 1995. |
| Assessment |
|
Exam. |