کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
1708369 | 1012822 | 2012 | 5 صفحه PDF | دانلود رایگان |
We reduce the problem of factoring a semiprime integer to the problem of (numerically) integrating a certain highly oscillatory function. We provide two algorithms for addressing this problem, one based on the residue theorem and the other on the (extended) Cauchy argument principle. We show that in the former algorithm, computing the residue of the function at a certain pole leads to us obtaining the factors of the semiprime integer. In the latter, we consider a contour integral for which we are able to obtain an analytical solution with several branches. The computational difficulty reduces to that of discovering the branch of the solution which gives the precise integral. We address this problem by numerically computing an upper and a lower bound of the integral and then considering the branch that fits these bounds. The time complexity of the algorithms is left as an open problem.
Journal: Applied Mathematics Letters - Volume 25, Issue 11, November 2012, Pages 1790–1794