new factorization algorithm

jasonp · 2012-06-17, 13:45

Described in an E-print 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 itself?

Period

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.

2012-06-17, 13:45	#1
jasonp Tribal Bullet Oct 2004 5×23×31 Posts	new factorization algorithm Described in an E-print 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.

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	2018-01-01 21:31
Doubt about P-1 algorithm	ET_	Software	20	2011-11-18 11:19
TF algorithm(s)	davieddy	Miscellaneous Math	61	2011-07-06 20:13
Dixon's algorithm	JHansen	Factoring	5	2005-03-15 21:35
Prime95's FFT Algorithm	Angular	Math	6	2002-09-26 00:13

2012-06-17, 19:27	#2
Raman 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

2012-06-17, 20:04	#3
jasonp Tribal Bullet Oct 2004 DED₁₆ 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.