M4219 completely factored?

[Prime95]

Originally Posted by WVU Mersenneer

How does the software determine if the cofactor is a probable prime?

I would like to know if the probable prime claim is valid thus rendering the remaining ECM work unnecessary.

Very nice find!!

Prime95 uses a simple Fermat PRP test. I think it uses three different bases. Highly likely the cofactor really is prime.

The number has been removed from the ECM pages -- well done.

[Raman]

During the past one year, three exponents had got their ever
"first known factor" being discovered.


p55 factor = 5198395892876421104415109549087087419559080537214372111 from M2269
p56 factor = 10788426156438350117334292343137689257142387557947087583 from M1657
p57 factor = 112493750443412941745410571996247741731544451845539488817 from M1669 by Dmitry Domanov

The first four Mersenne numbers, with no known factors at all are, thus:
M1061
M1237
M1277
M1619

Hope that they will also be factored off sooner itself!
M521 is prime, M523 had a larger sized factor. M1279 is prime, so that M1277 will thus have much larger enough factor?!

[WVU Mersenneer]

Originally Posted by Prime95

Very nice find!!

Prime95 uses a simple Fermat PRP test. I think it uses three different bases. Highly likely the cofactor really is prime.

The number has been removed from the ECM pages -- well done.

Dr Woltman, thank you for your very kind reply. I thank you for all the effort you've put in over the years for GIMPS which has allowed so many discoveries and advancements for mathematics, as well as something which I have immensely enjoyed for years. My thanks to you and all else who have contributed with code, theory, discussion, etc.

If I may trouble you with another question, does the server receive notification of a possible prime cofactor when found, does it perform the PRP test itself on recently-discovered factors in order to determine if an exponent has been fully-factored, or do you rely on us to ask about our finds in order to verify an exponent being fully-factored? I'm sure exponents are checked somehow, thus the exponents remaining on the ECM and factoring limits pages indeed need additional work in order to completely "solve" them.

My follow-up was prompted by:

[Tue Jan 11 01:56:39 2011]
ECM found a factor in curve #7, stage #2
Sigma=949404251897647, B1=50000, B2=5000000.
UID: /NEW_OMG, M86137 has a factor: 7747937967916174363624460881
Cofactor is a probable prime!

It's amazing to me that it is possible to determine that for the nearly 26,000-digit cofactor, and nearly instantaneously, too, though I am sure the math behind it is very well-known and straightforward to those who have been good-enough to reply to this thread, which is also amazing, as well as impressive.

My thanks again to all who have replied and to Dr. Woltman for making this possible in the first with his extraordinary project.

[ATH]

Originally Posted by WVU Mersenneer

It's amazing to me that it is possible to determine that for the nearly 26,000-digit cofactor, and nearly instantaneously, too, though I am sure the math behind it is very well-known and straightforward to those who have been good-enough to reply to this thread, which is also amazing, as well as impressive.

Congratulations on your find!

The co-factor is probable prime, its not proven prime. George said in post #12 that Prime95 does 3 Fermat PRP test in different bases, which is "simply" using Fermat's Little Theorem and testing that:

a^p-1 = 1 (mod p)

where p is the 25,902-digit cofactor, and a is 3 different small numbers. With 3 bases its highly likely prime >>99% I think, but I don't know how to calculate the odds.
http://primes.utm.edu/prove/prove2_2.html
http://mathworld.wolfram.com/FermatsLittleTheorem.html



The co-factor won't be proven prime just in the near future. The record for Primo certified prime is 12,903 digits:
http://www.ellipsa.eu/public/primo/t...ml#PrimoRecord

and for distributed computation the record is 20,562 digits:
http://primes.utm.edu/top20/page.php?id=27

[WVU Mersenneer]

Originally Posted by ATH

Congratulations on your find!

The co-factor is probable prime, its not proven prime. George said in post #12 that Prime95 does 3 Fermat PRP test in different bases, which is "simply" using Fermat's Little Theorem and testing that:

a^p-1 = 1 (mod p)

where p is the 25,902-digit cofactor, and a is 3 different small numbers. With 3 bases its highly likely prime >>99% I think, but I don't know how to calculate the odds.
http://primes.utm.edu/prove/prove2_2.html
http://mathworld.wolfram.com/FermatsLittleTheorem.html



The co-factor won't be proven prime just in the near future. The record for Primo certified prime is 12,903 digits:
http://www.ellipsa.eu/public/primo/t...ml#PrimoRecord

and for distributed computation the record is 20,562 digits:
http://primes.utm.edu/top20/page.php?id=27

ATH, Thank YOU very much for your reply, your congratulations, and especially for the links that I can follow in order to try to learn more about this, I very much appreciate it! Congratulations to you for what you have learned and know, and thank you for taking your time and offering a hand to someone like me who knows very little.

I am interested to see if Dr Woltman honors me with another reply to see how it is determined if an exponent has been fully factored, and also if this exponent ultimately "passes" the test.

[TimSorbet]

Originally Posted by WVU Mersenneer

... how it is determined if an exponent has been fully factored, and also if this exponent ultimately "passes" the test.

For M86137, that now hinges on the primality of the 25896-digit PRP cofactor. This is almost certainly prime, but can't be proven for some time, so we're currently not 100% certain that the full factorization is known. This exponent will only ultimately "pass" this test when the cofactor is proven prime.
By the way, Prime95 takes about 4-5 seconds to show this number PRP. PFGW takes about 30 seconds, and I've tested it to 3 bases: 3, 11, and 13.

Does anyone know the largest fully factored Mersenne number? Or the largest fully factored not-trivially-factored number? (assuming any large PRP cofactors are prime) I suspect this might be, or at least be close to, both of these. Edit: nope, after just a little digging, I found M86371, whose cofactor is PRP. From the closeness of these two, I doubt fully factored Mersennes this size are as rare as I guessed. But I do still wonder what the largest numbers like I said are...and also where all cofactors are known to be prime, not just PRP.
By the way, in looking for that, I found that a large number of primes between 86137 and 200000, 4971 out of 9611 to be exact, are not listed in PrimeNet's ECM progress report. I'm sure a few of those are just because they're fully factored, and 3 are because they're prime, but I'm not sure about the rest. Why is this? Is it that only numbers with some ECM progress are reported there?

[WVU Mersenneer]

Originally Posted by Mini-Geek

For M86137, that now hinges on the primality of the 25896-digit PRP cofactor. This is almost certainly prime, but can't be proven for some time, so we're currently not 100% certain that the full factorization is known. This exponent will only ultimately "pass" this test when the cofactor is proven prime.
By the way, Prime95 takes about 4-5 seconds to show this number PRP. PFGW takes about 30 seconds, and I've tested it to 3 bases: 3, 11, and 13.

Does anyone know the largest fully factored Mersenne number? Or the largest fully factored not-trivially-factored number? (assuming any large PRP cofactors are prime) I suspect this might be, or at least be close to, both of these.

Thank you, Mini-Geek, for adding more knowledge and explanation. You also ask a great question, and I am eager to know answers to it.

[R.D. Silverman]

Originally Posted by Mini-Geek

For M86137, that now hinges on the primality of the 25896-digit PRP cofactor. This is almost certainly prime, but can't be proven for some time, so we're currently not 100% certain that the full factorization is known. This exponent will only ultimately "pass" this test when the cofactor is proven prime.
By the way, Prime95 takes about 4-5 seconds to show this number PRP. PFGW takes about 30 seconds, and I've tested it to 3 bases: 3, 11, and 13.

Does anyone know the largest fully factored Mersenne number? Or the largest fully factored not-trivially-factored number? (assuming any large PRP cofactors are prime) I suspect this might be, or at least be close to, both of these.

I would consider a number that is the product of two primes, one of
which is less than 30 digits to be trivial to factor.

What do you mean by "trivial"???

You need to define "trivial".

[rogue]

If you can factor cofactor+1 or cofactor-1 to 33%, then PFGW can prove primality. I don't know how difficult that would be, but I suggest running some ECM curves against cofactor+1 and cofactor-1 to see if any of them can be factored into primes/prps and then doing it again.

For example, given cofactor x, presume x+1 (or x+1) is factored as xf1 * xf2 * xf3 with xf3 PRP. Now factor xf3+1 (or xf3-1). If that factors as xf31 * xf32* xf33 where all factors are prime, then it proves that xf3 is prime, which then proves that x is prime.

You can continue factoring with this method indefinitely.

I'm not saying that this will be easy to do, but one never knows...

[TimSorbet]

Originally Posted by R.D. Silverman

I would consider a number that is the product of two primes, one of
which is less than 30 digits to be trivial to factor.

What do you mean by "trivial"???

You need to define "trivial".

I would only consider that a trivial factorization if the primes were known in advance and the composite was formed by multiplying them together. I'll define a not trivially-factored number as such:
The number must not be prime, the number must not be of a form in which all factors are trivially known, such as x!, and the number can not have been originally formed by multiplying known primes and/or composites together. (forms such as x!+1 are non-trivial) By my definition, M86137 is not trivially factored, (and, indeed, every Mersenne number with p prime except Mersenne primes) but if you were to "factor" M1000*M11213*M43112609, that would be a trivial factorization.

Originally Posted by rogue

If you can factor cofactor+1 or cofactor-1 to 33%, then PFGW can prove primality. I don't know how difficult that would be, but I suggest running some ECM curves against cofactor+1 and cofactor-1 to see if any of them can be factored into primes/prps and then doing it again.

For example, given cofactor x, presume x+1 (or x+1) is factored as xf1 * xf2 * xf3 with xf3 PRP. Now factor xf3+1 (or xf3-1). If that factors as xf31 * xf32* xf33 where all factors are prime, then it proves that xf3 is prime, which then proves that x is prime.

You can continue factoring with this method indefinitely.

I'm not saying that this will be easy to do, but one never knows...

I think factoring either of the adjacent 25896-digit numbers to 33% (leaving at max ~17264 digit cofactors) would be FAR harder than proving the primality of the number by other means. Unless you get really lucky and one of them is factored very easily, including having the final PRP cofactor be small enough for you to prove prime by some means. But what's cool is that the DB lists the percentage that N-1 and N+1 are factored when you look at a PRP, and has an option to have it use one of those methods when it's factored enough. This number's N-1 and N+1 are factored 0.02% and 0.023%, respectively.

By the way, I edited this in to my post, but with all the posts after it since I put it in, I'll repost it so it doesn't get lost:

Originally Posted by Mini-Geek

Edit: nope, after just a little digging, I found M86371, whose cofactor is PRP. From the closeness of these two, I doubt fully factored Mersennes this size are as rare as I guessed. But I do still wonder what the largest numbers like I said are...and also where all cofactors are known to be prime, not just PRP.
By the way, in looking for that, I found that a large number of primes between 86137 and 200000, 4971 out of 9611 to be exact, are not listed in PrimeNet's ECM progress report. I'm sure a few of those are just because they're fully factored, and 3 are because they're prime, but I'm not sure about the rest. Why is this? Is it that only numbers with some ECM progress are reported there?

[henryzz]

Originally Posted by Mini-Geek

I think factoring either of the adjacent 25896-digit numbers to 33% (leaving at max ~17264 digit cofactors) would be FAR harder than proving the primality of the number by other means. Unless you get really lucky and one of them is factored very easily, including having the final PRP cofactor be small enough for you to prove prime by some means. But what's cool is that the DB lists the percentage that N-1 and N+1 are factored when you look at a PRP, and has an option to have it use one of those methods when it's factored enough. This number's N-1 and N+1 are factored 0.02% and 0.023%, respectively.

Neat feature. Applying some ecm and P-1 to N-1. Up to 0.09% factored very easily.
edit: no more coming really easily
will complete t20
edit2: gmp-ecm won't do stage 2 for ecm but will for p-1 so just doing stage 1 for some curves at 11000