Information Security Seminar 

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.