22/05/2009, 16:15 — 17:15 — Room P3.10, Mathematics Building
Paulo Mateus, IST and SQIG-IT
Reducing the Factorization of a Blum Integer to
theIntegrationofaHighly Oscillatory Function
We reduce the problem of factoring a Blum integer to the problem of
(numerically) integrating a certain meromorphic function. We
provide two algorithms to address this problem, one based on the
residue theorem and the other in the (generalized) Cauchy's
argument principle. In the former algorithm, we show that computing
the residue of the function at a certain pole leads to obtain the
factors of a Blum integer. In the latter, we consider a contour
integral that simplifies to an integral over the real numbers for
which we are able to obtain an analytical solution with several
branches. The computational hardness amounts to discovering the
branch of the solution that gives the precise integral. Joint on
going work with Vitor Rocha Vieira.
This seminar will be held in the Alameda campus!