Algebrai és aritmetikai algorimusok

    2007/2008 tavasz

Tematika

• Alapvetõ algoritmusok egész számokra és polinomokra:
  alapmûveletek, (kiegészített) euklideszi algoritmus,
  kínai maradéktétel
  Segédanyagok: V. Shoup, A Computational Introduction to Number Theory and Algebra  4. és 17. fejezetek (pdf)
  InfAalg18.1
  
• Prímtesztelés
  
  véletlent használó prímtesztek,
  az AKS-féle determiszitkus prímteszt
  Segédanyagok:
  (Rabin-Miller): V. Shoup, A Computational Introduction to Number Theory and Algebra  10. fejezet (pdf)
  (AKS): Rónyai Lajos fóliái (ps)
  Farkas Gábor és Kátai Imre Számelmélet. c. fejezete Iványi Antal (szerk) Informatikai Algoritmusok II. kötetébõl (22.5 rész)
  
• A gyors Fourier-transzformáció:
  
  behelyettesítés/interpoláció (kínai maradéktétel spec. esete),
  diszkrét Fourier-transzormáció, gyors Fourier-transzformáció,
  alkalmazás polinomok gyors szorzására
  Segédanyagok:
  FFT: S. Gao: Fast Fourier transforms and sparse linear systems over finite fields 2. és 3. lecke (pdf)
  gyors szorzás: D. J. Bernstein, Fast Multiplication And Its Applications 2. és 3. fejezetek (ps)
  
• Newton-iteráció
  
  polinomok egyszeres gyökeinek felemelése,
  alkalmazás polinomok osztására
  mátrixok Jordan-felbontása
  Segédanyag (osztáshoz): D. J. Bernstein, Fast Multiplication And Its Applications 6. és 17. fejezetek
  
• Polinomok felbontása véges testek felett:
  négyzetmentes faktorizáció,
  Berlekamp-részalgebra, abszolút Berlekamp-részalgebra,
  Berlekamp determinisztikus algoritmusa,
  a Cantor-Zassenhaus-algoritmus
  Segédanyagok: V. Shoup, A Computational Introduction to Number Theory and Algebra  20. fejezet (pdf)
  InfAlg18.3
  
• Az LLL bázisredukció:
  rácsok, bázis létezése,
  Gauss-algoritmusa, Lovász-redukció,
  redukált bázis tulajdonságai,
  legrövidebb vektor koordinátái redukált bázisban
  Segédanyagok:Oded Regev's Lattices in Computer Science  "Introduction és "The LLL algorithm" fejezetek (ps v. pdf)
  InfAlg18.4
  
• Polinomok felbontása a racionális számok felett:
  visszaveteztés egész együtthatós fõpolinomok felbontására,
  moduláris négyzetmentesség, jó prímek mérete,
  Hensel-felemelés, a Berlekamp-Zassenhaus-algoritmus,
  az LLL polinomfakrotizációs algoritmus 
  Segédanyagok: Madhu Sudan's lecture notes on Algebra and Computation 10., 3. és 7. leckék (ps)
  InfAlg18.5
  
• Egészek faktorizációja és a diszkrét logaritmus
  Faktorizáció: Pollard-féle ró-módszer; Dixon szubexpononciális algoritmusa; kvadratikus szita és számtest szita csak megemlítve
  Diszkrét log: Shanks baby step/giant step módszere; Pollard ró diszkrét logra; index-kalkulus csak megemlítve; (Hellman-Pohlig sajnos kimaradt) Segédanyagok: V. Shoup, A Computational Introduction to Number Theory and Algebra  11. és 15. fejezetek (pdf)
  

Vizsga:

1. Hagymányos vizsga a fenti tematikából
2. Beszámoló az alább felsorolt cikkek valamelyikébõl. Hogy ne mindenki ugyanazt válassza, elõzetes egyeztetés velem.
   

Választható irodalom: