| | |
| | |
Stat |
Members: 3667 Articles: 2'599'751 Articles rated: 2609
08 February 2025 |
|
| | | |
|
Article overview
| |
|
A babystep-giantstep method for faster deterministic integer factorization | Markus Hittmeir
; | Date: |
1 Sep 2016 | Abstract: | In 1977, Volker Strassen presented a deterministic and rigorous algorithm for
solving the problem to compute the prime factorization of natural numbers $N$.
His method is based on fast polynomial arithmetic techniques and runs in time
$widetilde{O}(N^{1/4})$, which has been state of the art for the last fourty
years. In this paper, we will combine Strassen’s approach with a
babystep-giantstep method to improve the currently best known bound by a
superpolynomial factor. The runtime complexity of our algorithm is of the form
[ widetilde{O}left(N^{frac{1}{4}-frac{log 2}{16(loglog N-log
4)}}
ight). ] | Source: | arXiv, 1608.8766 | Services: | Forum | Review | PDF | Favorites |
|
|
No review found.
Did you like this article?
Note: answers to reviews or questions about the article must be posted in the forum section.
Authors are not allowed to review their own article. They can use the forum section.
|
| |
|
|
|