Abstract:
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). |