- Meeting 11 : Wed, Sep 10, 02:00 pm-04:15 pm
References | |
Exercises | |
Reading | |
More algorithmic tasks on polynomials: The case of univariate polynomials. 1) Finding a root of a given polynomial. 2) Computing a factor of a given polynomial.
When does a polynomial have root in the underlying field?
Fundamental theorem of algebra. When do polynomials have unique factorization? Unique Factorization Domains.
Gauss's Lemma.
References: | See Notes here.
|
- Meeting 12 : Sun, Sep 14, 11:00 am-11:45 am
References | |
Exercises | |
Reading | |
Finite Fields, Field extensions and first properties.
References: | Notes Written by RP.
|
- Meeting 13 : Sun, Sep 14, 11:45 am-12:30 pm
References | |
Exercises | |
Reading | |
More on finite fields. The polynomial x^q-x. The distinct degree factorization problem.
References: | Notes Written by RP.
|
- Meeting 14 : Wed, Sep 17, 02:00 pm-04:00 pm
References | |
Exercises | |
Reading | |
Distinct degree factorization: Complete algorithm. Factorization of x^q-x.
- Meeting 15 : Thu, Sep 18, 04:30 pm-06:00 pm
References | |
Exercises | |
Reading | |
Structure of quotient rings: Chinese remaindering theorem.
Factorization over finite fields: Cantor-Zassenhaus Algorithm.
References: | Notes Written by RP. See Lectures 6 and 11. Also see [vGathen]
|
- Meeting 16 : Tue, Sep 23, 02:00 pm-04:00 pm
References | |
Exercises | |
Reading | |
Cantor-Zassenhaus (Contd). Overview of other factorization algorithms: Berlekamp's algorithm.
References: | Notes Written by RP.
|
- Meeting 17 : Wed, Sep 24, 02:00 pm-04:00 pm
References | |
Exercises | |
Reading | |
Berlekamp's algorithm.
References: | [vGathen] Book. Notes by RP.
|
- Meeting 18 : Tue, Sep 30, 02:00 pm-04:00 pm
References | |
Exercises | |
Reading | |
An application of factorization: Construction of BCH codes. Multivariate polynomials: Computing the GCD, resultants.
- Meeting 19 : Wed, Oct 01, 02:00 pm-03:30 pm
References | |
Exercises | |
Reading | |
Hensel's Lifting of factors and roots. Application to bivariate factorization.
References: | Notes by Madhu Sudan. Also see [vGathen]. Analogy with Newton Raphson is taken from Notes by RP.
|
- Meeting 20 : Wed, Oct 08, 02:00 pm-04:00 pm
References | |
Exercises | |
Reading | |
Bivariate factorization. Cleaning up the factors after Hensel Lifting.
References: | Notes by Madhu Sudan. For factoring over Z, see [vGathen].
|
- Meeting 21 : Thu, Oct 09, 04:30 pm-06:15 pm
References | |
Exercises | |
Reading | |
Factoring over integers. Mignotte's bound on coefficients. A factoring algorithm using large primes. Application of Hensel lifting. Introduction to Lattices.
- Meeting 22 : Sat, Oct 11, 09:00 pm-11:00 am
References | |
Exercises | |
Reading | |
Lattice basis reduction. Application to integer factoring. LLL algorithm (description)
- Meeting 23 : Thu, Oct 16, 04:30 pm-06:00 pm
References | |
Exercises | |
Reading | |
LLL algorithm: correctness proof.