Algebrai és aritmetikai algorimusok

1. Alapvető algoritmusok egész számokra és polinomokra:

   alapműveletek, (kiegészített) euklideszi algoritmus,

   kínai maradéktétel

2. Prímtesztelés

   a Rabin-Miller-féle véletlent használó prímteszt,

   az AKS-féle determiszitkus prímteszt

3. 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

4. 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

5. 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

6. 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