Name
Title | ||
|---|---|---|
Reducing factorization of a semiprime number to the integration of highly oscillatory functions. |
Abstract | ||
|---|---|---|
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. |
Year | DOI | Venue |
|---|---|---|
2012 | 10.1016/j.aml.2012.02.014 | Applied Mathematics Letters |
Keywords | Field | DocType |
Integration of highly oscillatory functions,Modular equations,Factorization | Semiprime,Mathematical optimization,Open problem,Mathematical analysis,Upper and lower bounds,Residue theorem,Methods of contour integration,Argument principle,Factorization,Time complexity,Mathematics | Journal |
Volume | Issue | ISSN |
25 | 11 | 0893-9659 |
Citations | PageRank | References |
0 | 0.34 | 1 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Paulo Mateus | 1 | 33 | 4.55 |
| V. R. Vieira | 2 | 0 | 0.34 |