Value of a factor

[ewmayer]

Originally Posted by preda

Now a magical genie (jinn) appears, and proposes you this trade: he would provide a factor for the exponent in question, in exchange for an amount of computation measured as a percent of one PRP test. What percent of one PRP are you willing to pay for a factor?

It depends - is the mystery datefactor good-looking? Does it have a warm personality, a good sense of humor? Is it a good cook?

More seriously:

Originally Posted by Prime95

I'd pay an extra 50% of a PRP test even for an ordinary looking 90ish-bit factor.

This may not be rational and is not best as far as GIMPS throughput goes, but for me it is a lot more satisfying to say "that Mersenne is composite, here's a factor" rather than "I ran a PRP test, and generated a proof file which I've since deleted, and it went through this process that I'm sure is secure and that process said the proof was valid, so that Mersenne number is really, really composite. Trust me".

It is indisputable that an explicit factor provides the most compact and easily verifiable proof of compositeness, so perhaps GIMPS should consider something along the lines you suggest to encourage those who enjoy searching for factors and developing improved algorithms to do so. OTOH, we don't want to encourage people to spend inordinate amounts of computational effort to search for factors, so such a scheme would necessarily be a balancing act. The credit formula should take into account existing credit formulae for factors found via TF and p-1 and be somewhat compatible with them, e.g. if I use (say) deeper-than-default p-1 and turn up a factor, the credit should increase with factor size, but in some logarithmic-style way such that it would take a truly impressive p-1 factor to yield, say, 50% the credit of a PRP test. Other issues:

1. Do we want to assign such credit only for the first-found factor for a known-composite M(p), or also offer credit for any others found?

2. Do we want to offer bonus credit for a factor which amounts to a complete factorization, i.e. for which the remaining cofactor is a PRP, even if the latter is too large to be rigorously provable with any reasonable effort?