mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2010-09-30, 22:40   #1
WVU Mersenneer
 
WVU Mersenneer's Avatar
 
Mar 2010
Morgantown, WV

1D16 Posts
Default M4219 completely factored?

I was lucky-enough 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 off-topic, what methods might http://www.numberempire.com/numberfactorizer.php use in order to nearly-instantaneously factor up to 60-digit numbers?

Thank you for helping me learn more through your answers or by pointing me in the right direction.
WVU Mersenneer is offline   Reply With Quote
Old 2010-09-30, 22:48   #2
alpertron
 
alpertron's Avatar
 
Aug 2002
Buenos Aires, Argentina

19·73 Posts
Default

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.
alpertron is offline   Reply With Quote
Old 2010-09-30, 22:58   #3
WVU Mersenneer
 
WVU Mersenneer's Avatar
 
Mar 2010
Morgantown, WV

29 Posts
Default

Quote:
Originally Posted by alpertron View Post
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.
Thank you very much, Alperton! I sincerely appreciate your congratulations, and I look forward to learning about the abbreviations you were generous-enough to provide me with as I don't wish to be merely a "hand waver", but I cannot begin to research that which I do not know exists.

Good luck to you with all of your GIMPS-related endeavors!
WVU Mersenneer is offline   Reply With Quote
Old 2010-09-30, 23:00   #4
retina
Undefined
 
retina's Avatar
 
"The unspeakable one"
Jun 2006
My evil lair

189E16 Posts
Default

Quote:
Originally Posted by WVU Mersenneer View Post
... is this cofactor, in excess of 1,140 digits, too large to ever prove prime?
This is easily provable as prime. Primo can do it, there are other programs also.
retina is offline   Reply With Quote
Old 2010-09-30, 23:10   #5
WVU Mersenneer
 
WVU Mersenneer's Avatar
 
Mar 2010
Morgantown, WV

29 Posts
Default

Quote:
Originally Posted by retina View Post
This is easily provable as prime. Primo can do it, there are other programs also.
Thank you, Retina, I will research this also.

How is it that programs such as Primo can prove large numbers to be prime, and yet a 320-digit 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.
WVU Mersenneer is offline   Reply With Quote
Old 2010-09-30, 23:14   #6
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

59×163 Posts
Default

I will have a Primo certificate for it just in case in half an hour.
Consider it proven.
Attached Files
File Type: zip M4219cofactor.zip (79.5 KB, 172 views)

Last fiddled with by Batalov on 2010-10-01 at 00:07 Reason: Cert. attached
Batalov is offline   Reply With Quote
Old 2010-09-30, 23:35   #7
retina
Undefined
 
retina's Avatar
 
"The unspeakable one"
Jun 2006
My evil lair

2·23·137 Posts
Default

Quote:
Originally Posted by WVU Mersenneer View Post
How is it that programs such as Primo can prove large numbers to be prime, and yet a 320-digit number such as M1061 remains without a known factor?
The answer is complex. Finding a factor and prime proving use different methods and techniques.

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.
retina is offline   Reply With Quote
Old 2010-10-01, 00:30   #8
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22×5×373 Posts
Default

Quote:
Originally Posted by WVU Mersenneer View Post
Thank you, Retina, I will research this also.

How is it that programs such as Primo can prove large numbers to be prime, and yet a 320-digit number such as M1061 remains without a known factor?

.
Question: Why do you believe that prime proving and factoring have
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 sub-exponential time; it is quite slow.
R.D. Silverman is offline   Reply With Quote
Old 2010-10-01, 00:44   #9
alpertron
 
alpertron's Avatar
 
Aug 2002
Buenos Aires, Argentina

19·73 Posts
Default

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 2010-10-01 at 00:46
alpertron is offline   Reply With Quote
Old 2010-10-01, 00:56   #10
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

746010 Posts
Default

Quote:
Originally Posted by alpertron View Post
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.
Yes. Dick Lehmer once made the comment that factoring will always
remain a hard problem, because any new algorithm is very quickly
pushed to its computational limit......
R.D. Silverman is offline   Reply With Quote
Old 2010-10-01, 01:05   #11
alpertron
 
alpertron's Avatar
 
Aug 2002
Buenos Aires, Argentina

25538 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
Yes. Dick Lehmer once made the comment that factoring will always
remain a hard problem, because any new algorithm is very quickly
pushed to its computational limit......
The hard problem will be to find enough disks to store all the extensions of the Cunningham tables!
alpertron is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
I'm not sure if this is prime or my CPU-Completely lost. Unregistered Information & Answers 4 2013-04-10 07:09
Factored vs. Completely factored aketilander Factoring 4 2012-08-08 18:09
Prime 95 Reccomended - Completely Lost MarkJD Information & Answers 10 2010-08-19 17:31
And now for something completely the same.... R.D. Silverman Programming 10 2005-08-17 01:45
M673 completely factored philmoore Factoring 1 2003-03-31 23:49

All times are UTC. The time now is 17:03.


Sat Dec 4 17:03:23 UTC 2021 up 134 days, 11:32, 1 user, load averages: 1.09, 1.30, 1.28

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.