20120617, 13:45  #1 
Tribal Bullet
Oct 2004
3·1,181 Posts 
new factorization algorithm
Described in an Eprint 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.

20120617, 19:27  #2 
Noodles
"Mr. Tuch"
Dec 2007
Chennai, India
3×419 Posts 
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 itself?
Period 
20120617, 20:04  #3 
Tribal Bullet
Oct 2004
3·1,181 Posts 
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.

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
18th Test of primality and factorization of Lepore in 5 * log_25 (N) (New Year's algorithm)  Alberico Lepore  Alberico Lepore  2  20180101 21:31 
Doubt about P1 algorithm  ET_  Software  20  20111118 11:19 
TF algorithm(s)  davieddy  Miscellaneous Math  61  20110706 20:13 
Dixon's algorithm  JHansen  Factoring  5  20050315 21:35 
Prime95's FFT Algorithm  Angular  Math  6  20020926 00:13 