Universitatea "Babeş-Bolyai" din Cluj-Napoca

Facultatea de Matematică şi Informatică
FISA DISCIPLINEI

Algebră computaţională şi teoria numerelor

Computational algebra and number theory

Cod	Semes- trul	Ore: C+S+L	Credite	Tipul	Sectia
MA027	5	2+1+0	5	optionala	Matematică-Informatică (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.

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	Assessment
Examen.	Exam.