Algebrai és aritmetikai algorimusok

    2007/2008 tavasz

Tematika

InfAalg18.x: Ivanyos Gábor és Rónyai Lajos "Algebra" c. fejezete Iványi Antal (szerk) Informatikai Algoritmusok II. kötetéből (838-892. old.)

Vizsga:

A vizsga helyét és idejét mindenki egyénileg velem egyeztesse e-mailen: Gabor.Ivanyos@sztaki.hu.

Három féle lehetõség közül lehet választani:
  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:

V. Shoup, New algorithms for finding irreducible polynomials over finite fields. (ps)
Mathematics of Computation 54:435-447, 1990.
Véges testek feletti determinisztikus polinomfaktorizáció és irreducibilis polinomok keresésének
kapcsolatáról.

E. Kalt ofen, Polynomial time reductions from multivariate to bi- and univariate integral polynomial factorization. (ps.gz)
SIAM J. Comput.
, 14(2):469-489, 1985.
Többváltozós polinomok faktorizációja.

D. F. Holt, S. Rees: Testing modules for irreducibility. (dvi vagy ps)
J. Australian Math. Soc. 57 (1994), 1-16.
A MeatAxe modulusok felbontására: a véges testek feletti polinomfaktorizáció alkalmazása.
A Wedderburn-féle struktúratételeket ismerõk számára.

M. Ajtai, The Shortest Vector Problem in L_2 is NP-hard for Randomized Reductions. (ps v. pdf)
ECCC TR997-047, Revision 1, pp. 1-33.
A legrövidebb rácsvektor megtalálásának nehézségérõl.


D. Micciancio, The Shortest Vector Problem is NP-hard to Approximate within some Constant. (ps v. pdf)
Proc. FOCS'98, 92-98.
Az approximáció is nehéz...

J. C. Lagarias, A. M. Odlyzko, Solving low-density subset sum problems. (pdf, ACM Digital Library hozzáférés kell)
Journal of the ACM 32 (1985), 229-246.
LLL redukció alkalmazása kódfeltörésre


V. Shoup, A Computational Introduction to Number Theory and Algebra  15.2 alfejezet
index-kalkulus algoritmus a diszkrét log problémára