20100930, 22:40  #1 
Mar 2010
Morgantown, WV
1D_{16} Posts 
M4219 completely factored?
I was luckyenough to get the following result on one of my computers:
[Sun Aug 15 19:00:26 2010] ECM found a factor in curve #252, stage #2 Sigma=7922693040963723, B1=3000000, B2=300000000. UID: /NEW_OMG, M4219 has a factor: 114993958477860428006858637956899699352321 Cofactor is a probable prime! How does the software determine if the cofactor is a probable prime? Will GIMPS attempt to verify this claim so as to remove M4219 from the ECM Progress report, or is this cofactor, in excess of 1,140 digits, too large to ever prove prime? As I have found the 2 largest reported factors for M4219, but the report shows it as still having 280 curves to be run at B1=3M, I would like to know if the probable prime claim is valid thus rendering the remaining ECM work unnecessary. Slightly offtopic, what methods might http://www.numberempire.com/numberfactorizer.php use in order to nearlyinstantaneously factor up to 60digit numbers? Thank you for helping me learn more through your answers or by pointing me in the right direction. 
20100930, 22:48  #2 
Aug 2002
Buenos Aires, Argentina
19·73 Posts 
Congratulations for the factor found!! For the last question I think it is using one of the programs YAFU or MSIEVE behind the PHP frontend. So it should be using SIQS algorithm.

20100930, 22:58  #3  
Mar 2010
Morgantown, WV
29 Posts 
Quote:
Good luck to you with all of your GIMPSrelated endeavors! 

20100930, 23:00  #4 
Undefined
"The unspeakable one"
Jun 2006
My evil lair
189E_{16} Posts 

20100930, 23:10  #5  
Mar 2010
Morgantown, WV
29 Posts 
Quote:
How is it that programs such as Primo can prove large numbers to be prime, and yet a 320digit number such as M1061 remains without a known factor? There is so much to learn, that so many of you know so much so readily...congratulations to you all. I thank George, too, for providing a place in this forum where you can share ideas and findings and where I and those like me can learn and benefit from it. 

20100930, 23:14  #6 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2
59×163 Posts 
I will have a Primo certificate for it just in case in half an hour.
Consider it proven. Last fiddled with by Batalov on 20101001 at 00:07 Reason: Cert. attached 
20100930, 23:35  #7  
Undefined
"The unspeakable one"
Jun 2006
My evil lair
2·23·137 Posts 
Quote:
How is it that we can prove M43112609 is prime but we can't factor M1061? Because the LL test does not find factors. It merely proves that no factors exist. 

20101001, 00:30  #8  
Nov 2003
2^{2}×5×373 Posts 
Quote:
the same difficulty. Your question has a simple answer: prime proving runs in polynomial time. And probable prime testing runs even faster. Factoring runs in subexponential time; it is quite slow. 

20101001, 00:44  #9 
Aug 2002
Buenos Aires, Argentina
19·73 Posts 
Bob is right, but it is clear that for this kind of projects, factoring or proving primality will be always slow, even if a polynomial time factoring algorithm is found and being used, because in that case the participants will be busy trying to completely factor the number floor(pi*10^10000000), the 24th Fermat number or some other large integers.
Last fiddled with by alpertron on 20101001 at 00:46 
20101001, 00:56  #10  
Nov 2003
7460_{10} Posts 
Quote:
remain a hard problem, because any new algorithm is very quickly pushed to its computational limit...... 

20101001, 01:05  #11 
Aug 2002
Buenos Aires, Argentina
2553_{8} Posts 
The hard problem will be to find enough disks to store all the extensions of the Cunningham tables!

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
I'm not sure if this is prime or my CPUCompletely lost.  Unregistered  Information & Answers  4  20130410 07:09 
Factored vs. Completely factored  aketilander  Factoring  4  20120808 18:09 
Prime 95 Reccomended  Completely Lost  MarkJD  Information & Answers  10  20100819 17:31 
And now for something completely the same....  R.D. Silverman  Programming  10  20050817 01:45 
M673 completely factored  philmoore  Factoring  1  20030331 23:49 