M4219 completely factored?

WVU Mersenneer · 2010-09-30, 22:40

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.

alpertron · 2010-09-30, 22:48

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.

WVU Mersenneer · 2010-09-30, 22:58

Quote:

Originally Posted by alpertron

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!

retina · 2010-09-30, 23:00

Quote:

Originally Posted by WVU Mersenneer

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

WVU Mersenneer · 2010-09-30, 23:10

Quote:

Originally Posted by retina

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.

Batalov · 2010-09-30, 23:14

I will have a Primo certificate for it just in case in half an hour.
Consider it proven.

retina · 2010-09-30, 23:35

Quote:

Originally Posted by WVU Mersenneer

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.

R.D. Silverman · 2010-10-01, 00:30

Quote:

Originally Posted by WVU Mersenneer

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.

alpertron · 2010-10-01, 00:44

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.

R.D. Silverman · 2010-10-01, 00:56

Quote:

Originally Posted by alpertron

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

alpertron · 2010-10-01, 01:05

Quote:

Originally Posted by R.D. Silverman

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!

2010-09-30, 22:40	#1
WVU Mersenneer Mar 2010 Morgantown, WV 35₈ Posts	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.

2010-10-01, 00:44	#9
alpertron Aug 2002 Buenos Aires, Argentina 2·11·61 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(pi10^10000000), the 24th Fermat number or some other large integers. Last fiddled with by alpertron on 2010-10-01 at 00:46*

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

2010-09-30, 22:48	#2
alpertron Aug 2002 Buenos Aires, Argentina 2·11·61 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.