University of Calgary

Towards a new Subexponential Factoring Algorithm

Submitted by jlongwor on Mon, 04/19/2010 - 9:11am.
Apr 23 2010 - 3:00pm
Apr 23 2010 - 3:50pm
Speaker: 

Francesco Sica, visiting Professor

Location: 
MS 431

I will explain how to use classical complex analytic methods in order to arrive at a deterministic polynomial-time reduction of the problem of factoring to the computation of some multiple series. The main idea is to compute to a sufficient precision a multiplicative function which depends on N. This is done by introducing its generating function, which is a product of Riemann zeta functions. The functional equation is the analytic translation of the needed arithmetic information, which leads, up to some easily computable terms, to some explicit multiple series, which represent the computational bottleneck of this approach. The method itself contains many technicalities, which I will avoid, but I will try to present the main challenges encountered and how I overcame them. There remains to evaluate a particular kind of multiple series, which I called the great singular series.