| Algebră computaţională şi teoria numerelor |
trul |
|||||
| Cadre didactice indrumatoare |
| Prof. Dr. MARCUS Andrei, marcus@math.ubbcluj.ro |
| Obiective |
|
Prezentarea unor algoritmi fundamentali cu aplicatii in teoria numerelor. Discutia complexitatii acestor algoritmi. Accentul va fi pus pe teste de primalitate si algoritmi de factorizare. |
| Continut |
|
I. Congruente si clase de resturi
1. Complexitatea algoritmilor, notatia O 2. Algoritmul lui Euclid 3. Congruente ( Teorema lui Euler, Teorema lui Fermat, Teorema Chineza a resturilor, Rezolvarea congruentelor si sistemelor de congruente de gradul intii 4. Grupul (U(Zn);) Radacini primitive si indici. Rezolvarea congruentelor binome 5. Resturi patratice. Simbolul lui Legendre II. Teste de primalitate si factorizare 1. Metode elementare. Numere pseudoprime 2. Metoda Monte-Carlo 3. Metoda Fermat 4. Metoda fractiilor continue 5. Metoda sitei patratice si metoda lui Pollard III. Polinoame peste corpuri finite 1. Corpuri finite Logaritmul discret 2. Polinoame ireductibile 3. Factorizarea polinoamelor. Algoritmul lui Berlekamp IV. Alti algoritmi 1. Adunarea rapida 2. Transformarea Fourier rapida 3. Baze Gröbner. Algoritmul lui Buchberger 4. Generatorr si relatii in grupuri. Algoritmul Todd-Coxeter 5. Algoritmul LLL |
| Bibliografie |
|
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. |
| Evaluare |
|
Examen. |