mersenneforum.org

mersenneforum.org (https://www.mersenneforum.org/index.php)
-   Math (https://www.mersenneforum.org/forumdisplay.php?f=8)
-   -   new factorization algorithm (https://www.mersenneforum.org/showthread.php?t=16905)

jasonp 2012-06-17 13:45

new factorization algorithm
 
Described in [url="http://eprint.iacr.org/2012/097"]an E-print[/url] from this year. The algorithm looks very much like the AKS primality test modified to find factors. Unfortunately the basic version described has about as much chance of being useful as the AKS test does.

Raman 2012-06-17 19:27

Does this algorithm belong to P (deterministic polynomial time, as well), as the AKS algorithm does, or otherwise is it being worser than even the subexponential running time algorithm [COLOR=black]itself?[/COLOR] [COLOR=black]
[/COLOR]
[COLOR=black]
[COLOR=LemonChiffon]Period[/COLOR]
[/COLOR]

jasonp 2012-06-17 20:04

The most honest answer is that nobody knows. You have to find a magic number such that a polynomial modular exponentiation yields a nontrivial GCD with n, and their experiments show that such a magic number is often a lot smaller than the smallest factor of n. But the most that they prove is that a magic number requires a number of tests equal to the smallest factor of n in the worst case, so the most we know is that the algorithm has exponential runtime at worst.


All times are UTC. The time now is 20:30.

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.