mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math

Reply
 
Thread Tools
Old 2012-06-17, 13:45   #1
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

DD716 Posts
Default 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.
jasonp is offline   Reply With Quote
Old 2012-06-17, 19:27   #2
Raman
Noodles
 
Raman's Avatar
 
"Mr. Tuch"
Dec 2007
Chennai, India

4E916 Posts
Default

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
Raman is offline   Reply With Quote
Old 2012-06-17, 20:04   #3
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

3×1,181 Posts
Default

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.
jasonp is offline   Reply With Quote
Reply

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 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

All times are UTC. The time now is 11:15.


Sun Dec 5 11:15:06 UTC 2021 up 135 days, 5:44, 0 users, load averages: 1.59, 1.30, 1.51

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

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.