Value of a factor

[preda]

Let's play this theoretical trading game:

Let's say you completed PRP on some exponent. The result was "composite". The PRP has been verified.

At this point you're sure the M(exponent) in question is composite. You do not doubt this fact a bit; but you don't have a factor.

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?

[Note, we're talking about a factor of an already established-composite number, so the factor does not contribute to deciding primality.]

At one extreme, you may answer: I already know that the candidate is composite, so I have no need for a factor; I'm willing to pay 0% (of one PRP test) for a factor.

In the other direction, you may answer: even though I know it's composite, I consider a factor so cool in itself that I'm willing to pay ... this much % of one PRP for it.

So, how much are you willing to pay for a factor for its own sake? Please post your amount (as a percentage of one PRP test) below.

PS: maybe this should be turned into a poll?

[retina]

A "percent of one PRP test" is not fixed value. So the cost is unknown at the time of the transaction.

Anyone entering into a contract for unknown costs would need to be crazy.

So the genie is a trickster. DON'T DO ANY BUSINESS WITH IT.

[preda]

Originally Posted by retina

A "percent of one PRP test" is not fixed value. So the cost is unknown at the time of the transaction.

Anyone entering into a contract for unknown costs would need to be crazy.

So the genie is a trickster. DON'T DO ANY BUSINESS WITH IT.

The "price" of a factor depends on the exponent. One simple way to model that is to take the price relative to the PRP for the same exponent, then the magnitude of the exponent is removed from the price.

I imagine, if I took 1h to complete the PRR, or 1day, or 1month, I would probably also pay different (proportional?) amounts for a factor.

[preda]

The first data-point (to break the ice):

I would pay 5% for a factor. Maybe even a bit more, but clearly not more than 10%.

[R. Gerbicz]

Originally Posted by preda

What percent of one PRP are you willing to pay for a factor?

A lot, maybe even 800% or more (for small exponent). Why? Because for semi prime Mersenne number even a single factor means that you have a full factorization. OK, without the proof that the factors are prime, but we have not that many full factorizations for Mersenne numbers.

[preda]

Originally Posted by R. Gerbicz

A lot, maybe even 800% or more (for small exponent). Why? Because for semi prime Mersenne number even a single factor means that you have a full factorization. OK, without the proof that the factors are prime, but we have not that many full factorizations for Mersenne numbers.

What about wavefront exponents (around 100M) ? Let's say one PRP takes on the order of days there (1day on GPU). Would you pay 8x just to get one factor of a random exponent, when you could complete 8 PRP tests instead? (would you rather have one factor, vs. having the primality status of 8 candidates?)

[R. Gerbicz]

Originally Posted by preda

What about wavefront exponents (around 100M) ?

When you have the proof scheme then probably nothing, but say 1% if you have no proof scheme (it is still too generous as the prp has much less than 1% failure).
One advantage of a factor is that you can check it in linear time that d | Mp.

You could say that it is pure theory, we haven't seen such things in Maths, then see this: https://hal.inria.fr/inria-00181029v1/document they provided a polynomial factor (the smallest degree divisor) for all reducible polynomial, much faster than the previous methods (if we count the time per polynomial).

[Alex]

Upto 100% for ordinary exponent, because thit is better than Double-check.

Perhaps, the same price for each next factor of the same exponent, because this may be the only way to full factoring.

And much more for small exponents, because their full factorings are more actual.
For example, I calculated, 4624984171798410% has been already spent on M1277.

[Ensigm]

If we consider factoring as goal that will eventually be reached (regardless of its relative priority to determining primality), then the percentage is certainly much more than 100%, given the algorthms we currently have. The expected amount of computation needed to find one factor for all composite mersenne numbers under a considerable exponent, say 100000, will certainly exceed (and might have already exceeded) the amount of computation needed to run a primality test on all of them. Many will succumb to TF, P-1, or ECM curves with small bounds, but there are a few diehards which have no small factors at all, inflating the overall average. So if we do the deal repeatedly with the genie at 100% for every composite mersenne number under a certain bound, we will almost certainly profit (in terms of computational output——We will lose the excitement, of course).

[Uncwilly]

Originally Posted by Alex

Upto 100% for ordinary exponent, because thit is better than Double-check.

But with the new advance of PRP with VDF and then running a Cert on that we will eliminate the need for a full DC. We will be spending ~5% or less extra time to verify the PRP run.

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