Universidade do Minho  

Mapa do Site
Reducing the Factorization of a Blum Integer to the Integration of a Highly Oscillatory Function

Resumo: 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 (CFIF/DF-IST).
  © 2024 Universidade do Minho  - Termos Legais  - actualizado por CMAT Símbolo de Acessibilidade na Web D.