Next: Repeated Squaring

Discrete Math, Fourteenth Problem Set (July 18)
REU 2003

Instructor: László Babai
Scribe: Ivona Bezakova

Repeated Squaring
Factoring of integers
Types of randomized algorithms
Representing a prime as a sum of two squares
Deterministic test of irreducibility of polynomials over ${\mathbb{F}}_p$
Las Vegas factoring of quadratic polynomials over ${\mathbb{F}}_p$
Back to the problem
Factoring integers in time, exponential in $\sqrt{n\log n}$
About this document ...

Varsha Dani 2003-07-25