Algebră computaţională şi teoria numerelor | Computational algebra and number theory |
trul |
|||||
(Mathematics-Computer Science) |
Cadre didactice indrumatoare | Teaching Staff in Charge |
Prof. Dr. MARCUŞ Andrei, marcus@math.ubbcluj.ro |
Obiective | Aims |
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. |
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. |
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 |
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 | Assessment |
Examen. |
Exam. |