Universitatea "Babes-Bolyai" Cluj-Napoca
Facultatea de Matematica si Informatica
FISA DISCIPLINEI

Algebră computaţională şi teoria numerelor
Cod
Semes-
trul
Ore: C+S+L
Credite
Tipul
Sectia
MA027
5
2+1+0
5
optionala
Matematică-Informatică
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.