Computer Science
Tel-Aviv University

0368.3382
Seminar on primality testing

Spring 2008

 

Announcements

  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

Info

When and where: Sunday 13:00-15:00, Schreiber 006.

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 ]