Speaker:
Petteri Kaski

Title:
Moderately-exponential-time integer factorization

Abstract:

The task of factoring a given integer into its prime factors occupies a tantalizing position in the study of algorithmics. While no polynomial-time algorithms are known for integer factorization, seemingly closely related problems such as the task of testing a given integer for primality, and the
task of factoring a univariate polynomial with coefficients in a finite field into its irreducible factors, do admit randomized polynomial-time algorithms. This talk will look at randomized algorithm designs for integer factoring, with the goal of developing Dixon’s (1981) random squares method, which factors any large integer N in expected time exp(O((ln N ln ln N)^{1/2})).

**

Helsinki Algorithms Seminar is a weekly meeting of researchers in the Helsinki area interested in the art of algorithms and algorithm design, broadly interpreted to cover both theoretical ideas and algorithm engineering on concrete computing platforms. In most cases we have a presentation prepared for each meeting to communicate an idea, a recent result, work-in-progress, or demo, but this should not be at the expense of discussion and simply having fun with algorithms.

Our affiliations are with Aalto University and the University of Helsinki, and accordingly our activities alternate between the Otaniemi Campus of Aalto University and the Kumpula Campus of University of Helsinki, catalyzed by the Helsinki Institute for Information Technology HIIT, under the Algorithmic Data Analysis (ADA) programme.

For the season programme, please see the seminar webpage.