# 0368.3382Seminar on primality testing

## Spring 2008

### Announcements

• Please notice: Our meeting room has changed to Schrieber 006.

• There will be no class on Sunday, 15.5 (I'm abroad) and on Sunday, 8.6 (Erev Shavuot).

• There will be three additional seminars on Fridays.

1. Friday, 13.6, 10-12, Schreiber 309

2. Friday, 27.6, 10-12, Schreiber 309

3. and Friday 18.7, 10-12 , Schreiber 309

### Instructor: Amnon Ta-Shma, Schreiber 127

Open to: undergraduates and graduate students. Each student will give one talk.

Grading: Based on participation in class and quality of presentation.

### Course material:

We will follow the book "Primality testing in Polynomial time" by Martin Dietzfelbinger.

Our goal (and the book's goal) is to explain M. Agrawal, N. Kayal and N. Saxena

deterministic polynomial time algorithm for primality testing.

### Lectures

 Date Topic 11.5.08 אריאל נגרין יאיר אסא 1 Basic arithmetic operations. Modular arithmetic. Fast exponentiation. (Sec 2.3) The GCD algorithm (Sec 3.2, but with matrix multiplication). Inverse in Zn*. 25.05.08 תמיר דוד אינה קלפ 2 The Chineese Remainder theorem. Euler's totient function φ(n) (Sec 3.4) Groups. Rings. Fields. Order. Basic facts. Cyclic groups. For every field F, F* is cyclic. The number of generators of Zp. (Chapter 4) 1.06.08 טל קמניקר ירון הגר 3 The density of primes (Sec 3.6) 8.06.08 Erev Shavuot. Friday 13.06.08 Hashlama טל שלו יונתן אביצור 4 The Miller Rabin Test (Chapter 5) 15.06.08 איל סגליס טל ילון 5 The Solovay-Strassen Test (Chapter 6) 22.06.08 אינה דוידוב מרגריטה וולד 6 Polynomails over rings. Arithmetic over polynomials. Computing GCD of polynomials. Irreducible polynomials. Finite fields. (Chapter 7) Friday 27.06.08 Hashlama יגאל לזרב רועי כהן 7 The Arithmetic Circuit Identity Testing problem (ACIT): [ACIT, first variant]: all evaluations are zero [ACIT , second variant]: all coefficients are zero ACIT, first variant, is coNP-complete. ACIT, second variant, is in coRP. Possible ref:Kabanets and Impagliazzo: Derandomizing Polynomial Identity Tests Means Proving Circuit Lower Bounds. Sec 2.3,2.4. 29.06.08 אלכס פונר רן רוזנטל 8 The AKS algorithm. (Sec 8.1) Time analysis. (Sec 8.3) 06.07.08 רוני ברקת אליעד צפדיה 9 Correctness proof. (Sec 8.4) 13.07.08 ליאור ליכט לירון רז תומר לוינבוים 10 The GUV condenser.V. Guruswami, C. Umans, and S. Vadhan. Unbalanced Expanders and Randomness Extractors from Parvaresh-Vardy Codes. Sec 3.1 Friday 18.7.08 Hashlama מורן רבר אנדרי קוכרנקו 11 Z. Dvir. On the size of Kakeya sets in finite fields. J. of the AMS (to appear)., 2008. [ bib | .pdf ]