Mersenne number with exponent 333333367 is composite

[ATH]

Originally Posted by lukerichards

Probably factored meaning that the factors have passed PRP tests?

Probably fully factored means that the cofactor is a PRP not proven prime, so there is a slight chance/risk it is not prime.

[GP2]

Originally Posted by lukerichards

Probably factored meaning that the factors have passed PRP tests?

All of the factors of Mersenne numbers that we are capable of finding are small enough that they can be trivially be proven prime. It is only the cofactor, the part that remains after dividing by all known factors, that sometimes tests PRP.

In all the cases where an exponent of nontrivial size has been determined to be fully factored or probably fully factored, we have a pattern of N small factors and one humungous cofactor that passes a PRP test. The cofactor's bit length is usually 99%+ of the bit length of the Mersenne number itself.

Needless to say, the overwhelming majority of numbers do not have such an extremely asymmetric pattern for their factors, where a single factor is nearly the same size as the number itself and all other factors are relatively tiny. So findable PRPs become very rare indeed as the Mersenne exponents get larger.

[Mysticial]

Originally Posted by GP2

It's "factored" because at least one factor is known.

If we knew all the factors, then it would be "fully factored". Out of the tens of millions of Mersenne numbers we have tested, only 332 of them are fully factored (or strongly believed to be). This number slowly increases, since new factors are found all the time.

The largest exponent for which the Mersenne number is proven to be fully factored is 63,703. The largest exponent which is probably fully factored is 7,313,983.

Isn't the largest Mersenne number that's fully factored just M51? The factors are 1 and itself.

[Madpoo]

Originally Posted by TheGuardian

PS. May I ask how these huge numbers came to be factored? Surely most deterministic algorithms would take ages to complete.

For instance, the exponent 333333367 is listed as "Factored", yet only 2 factors are known. Clearly, then the Mersenne number M333333367 is *not* factored. What am I missing?

FYI, I didn't see it mentioned by anyone else, but the two known factors for that exponent are both relatively small.

https://www.mersenne.ca/exponent/333333367

The smaller would have been found by only trial factoring to 37 bits, and the second one by TF to 49 bits. Doing either of those tests are trivial and would have finished in (seconds? couple minutes)?

Being so easy to find, those 2 factors were discovered a long long time ago so we don't even have a record of who found them. That's the case for most small factors (anything under 60'ish bits. The only exception is for secondary/tertiary/etc. factors which we might have more details on. In many cases, when the first factor was found nobody bothered checking for more, but people started doing that more recently (last 10-15 years).

At any rate, you provide a good example, although an unfortunate one, of why it's always a good idea to do a good amount of factoring (TF and P-1) on a # before committing yourself to something that could take months (or years in some cases).

I'm actually just about done with a mini-project where I took a couple thousand assignments that didn't have any P-1 testing done on them at all. Most of them are 332M+ exponents, so they really should have done at least a basic P-1 check.

I was doing just the basic B1=B2=100,000 which doesn't take much time... maybe a couple hours tops on a run of the mill desktop computer.

Of the tests I've done, I've probably managed to find a factor in about 1 out of 120 or so tests (just guesstimating there, I wasn't really keeping track).

For the most part, these are assignments that were made several years ago and they never actually started, or didn't check in any progress. But I'd hate to think that someone was toiling away for years and years, and meanwhile there was a factor that would have taken them a couple hours to find.

In reality, before doing a 100 million digit test, you'd want to do a P-1 test to the recommended bounds, which are picked to give it as good a chance as possible at finding a factor, considering the time it will take to do a first and second LL test.

Of course nowadays we'd recommend doing a PRP test instead, using the highly-reliable Gerbicz error checking. Because you don't want to spend all that time doing an LL test that had an error along the way, requiring *two* more tests to confirm.

[TheGuardian]

Originally Posted by kriesel

Welcome to the hunt, TheGuardian. What gpu do you have? I hope you're running no earlier than the May 2017 version of CUDALucas.

"Factored" in the GIMPS context means, at least one known prime factor found, and confirmed, so the exponent is ruled out as a possible Mersenne prime, no need to
a) trial factor any further,
b) P-1 factor,
c) attempt LL primality test or PRP probable-prime test,
d) double check whichever of LL or PRP were done in c preceding.
Finding a factor is a welcome result, because it saves a lot of computing time.

"Factored" is quite different from and a lower standard than "fully factored".

To apply your gpu to needed work, and improve your chances of avoiding unneeded duplication of someone else's work, go to https://www.mersenne.org/manual_assignment/ or https://www.mersenne.org/manual_gpu_assignment/
To report the results, copy and paste into https://www.mersenne.org/manual_result/
You may find some of the content at https://www.mersenneforum.org/forumdisplay.php?f=154 useful background info.
New user guidance draft https://www.mersenneforum.org/showpo...3&postcount=11
Specific to the many techniques used to make trial factoring fast, see https://www.mersenneforum.org/showpo...23&postcount=6

Thank you very much for your helpful post.

[kriesel]

Originally Posted by TheGuardian

Thank you very much for your helpful post.

You're welcome. Any suggestions how to make the existing info easier to find? Where did or would you look for it? Your new participant perspective is useful.

[paulunderwood]

? Mod(2,91333342559)^333333367
Mod(1, 91333342559)
? ##
  ***   last result computed in 0 ms.

It pays to know that some trial factoring and P-1 factoring has been done, before embarking on a test (that takes a year) -- and a PRP test is preferable to an LL test.

[TheGuardian]

I tried to submit my CUDALucas results.txt file on the mersenne.org website, but I get the error

"No CPU credit given for test of already factored"

What can I do?

[kriesel]

Originally Posted by TheGuardian

I tried to submit my CUDALucas results.txt file on the mersenne.org website, but I get the error

"No CPU credit given for test of already factored"

What can I do?

I think you're stuck. It's not giving credit for work that was not needed, because the number already had known factors. (I get you didn't know that at the time.)
If you want to rack up some computing credit fast on your gpu, get acquainted with the latest version of mfaktc, and run it on manual assignments. Assuming your gpu is somewhat like a GTX1060, it will produce about 15 times as much computing credit per day doing TF as doing LL or P-1. Tune it per directions in the mfaktc thread for maximum production rate.

[kriesel]

Originally Posted by Madpoo

In reality, before doing a 100 million digit test, you'd want to do a P-1 test to the recommended bounds, which are picked to give it as good a chance as possible at finding a factor, considering the time it will take to do a first and second LL test.

Of course nowadays we'd recommend doing a PRP test instead, using the highly-reliable Gerbicz error checking. Because you don't want to spend all that time doing an LL test that had an error along the way, requiring *two* more tests to confirm.

Good advice. Except there is no GIMPS software available for PRP on CUDA, or on NVIDIA's flavor of OpenCl, so no PRP on NVIDIA.

[TheGuardian]

Originally Posted by kriesel

I think you're stuck. It's not giving credit for work that was not needed, because the number already had known factors. (I get you didn't know that at the time.)
If you want to rack up some computing credit fast on your gpu, get acquainted with the latest version of mfaktc, and run it on manual assignments. Assuming your gpu is somewhat like a GTX1060, it will produce about 15 times as much computing credit per day doing TF as doing LL or P-1. Tune it per directions in the mfaktc thread for maximum production rate.

Thank you, I will try that.