Double check of factoring??

[petrw1]

I understand that LL/DC errors (i.e. incorrect results) are generally caused by hardware errors.

Is it not possible, likewise, for similar hardware errors to cause invalid factor results; i.e. reporting a factor when there really isn't one and thereby eliminating the exponent from LL/DC, erronously?

[sdbardwick]

IIRC, the server checks the validity of the factor when reported.

[CRGreathouse]

Originally Posted by petrw1

Is it not possible, likewise, for similar hardware errors to cause invalid factor results; i.e. reporting a factor when there really isn't one and thereby eliminating the exponent from LL/DC, erronously?

It's easy to check that the submitted factors are correct. The only kind of error you'd need to worry about is that no factor is reported when there is, in fact, a small factor. But even then the only cost is that the number will need to be LL'd.

[cheesehead]

Originally Posted by petrw1

Is it not possible, likewise, for similar hardware errors to cause invalid factor results;

Yes ...

i.e. reporting a factor when there really isn't one and thereby eliminating the exponent from LL/DC, erronously?

... but, unlike the situation with LL tests, factor verification doesn't require a rerun of the entire process (TF, P-1, ECM, ...) by which the factor was found. A split-second arithmetic calculation is all that's required, and (as sdbardwick pointed out) the server does that whenever it receives a factor-found report.

[chalsall]

Originally Posted by cheesehead

Yes ...

... but, unlike the situation with LL tests, factor verification doesn't require a rerun of the entire process (TF, P-1, ECM, ...) by which the factor was found. A split-second arithmetic calculation is all that's required, and (as sdbardwick pointed out) the server does that whenever it receives a factor-found report.

Yes... But...

This will detect false positives, but not false negatives...

[cheesehead]

Originally Posted by chalsall

This will detect false positives,

... which is exactly what the OP meant by "i.e. reporting a factor when there really isn't one and thereby eliminating the exponent from LL/DC, erronously", which I quoted in my reply. :-)

[chalsall]

Originally Posted by cheesehead

... which is exactly what the OP meant by "i.e. reporting a factor when there really isn't one and thereby eliminating the exponent from LL/DC, erronously", which I quoted in my reply.

Yes... Sorry.

But... a LL is *very* expensive.

Thus, while a false negative won't allow a prime to be missed, it would waste resources.

I have always wondered why Prime95 doesn't return a residual for factoring work which could only be produced by doing the full amount of work without error.

This would allow "spot checks" of factoring producers (at least, those using Prime95), which was the point I was trying to make.

[Mini-Geek]

Originally Posted by chalsall

Yes... Sorry.

But... a LL is *very* expensive.

Thus, while a false negative won't allow a prime to be missed, it would waste resources.

I have always wondered why Prime95 doesn't return a residual for factoring work which could only be produced by doing the full amount of work without error.

This would allow "spot checks" of factoring producers (at least, those using Prime95), which was the point I was trying to make.

Unless I'm mistaken, the odds of a false negative TF would be so astronomically lower than the odds of an incorrect LL residue that it's really just not worth the effort to double check.
Let's say you've got hardware that has a 2% chance of a single error over 30 days of work (be it TF or LL). For simplicity's sake, we'll assume an error on a TF always produces a negative for the factor being checked.
Let's say you make one computation error during a TF to 2^64. There's a 1/64th chance (assuming http://www.mersenne.org/various/math.php is right) of there being a factor anywhere in there. According to http://mersenne-aries.sili.net/throughput.php?cpu=AMD+Athlon%28tm%29+64+X2+Dual+Core+Processor+4800%2B|512|0&mhz=2500, there are about 1,136,364 TF iterations in that range. I'm not sure if 1 iteration=1 factor, but let's assume so. So there's about a 1/(64*1,136,364) chance that the one computation error was during a factor, rendering a false negative. That's a 0.000001375% chance of a missed factor for every error your computer makes. And this CPU could do about 389 TFs to 2^64 per 30 days. That means that there's a 2% chance that one out of 389 TFs would have a tiny chance of a missed factor, or a 0.000000000275% chance of a missed factor. Unless I'm making some false assumptions, or have done something really stupid here, I'd say that's well worth the risk, despite the large cost difference between LL and TF.

[chalsall]

Originally Posted by Mini-Geek

Unless I'm mistaken, the odds of a false negative TF would be so astronomically lower than the odds of an incorrect LL residue that it's really just not worth the effort to double check.

But we've already seen many instances of ranges which were TFed (using other software, admittedly) which then needed to be retested.

These were only found by way of statistical analysis (and perhaps this is the most optimal way -- I don't know).

But I stand by my argument that it *might* be good if the Prime95 client returned a unique residual even for TF work.

After all, if LL and DC work fails to execute deterministically on the CPUs out there, surely TF (and P-1 and ECM) work does as well?

And I'm not arguing for a standard "Double-check" of TF work. Simply the ability to do so for participants and/or machines which *might* be questionable. After all, a single bad machine can result in *many* bad results. And a bad participant can result in many *many* bad results.

Those far more learned than myself might be able to speak to this question more deeply.

[cheesehead]

Originally Posted by Mini-Geek

Unless I'm mistaken, the odds of a false negative TF would be so astronomically lower than the odds of an incorrect LL residue that it's really just not worth the effort to double check.

< snip >

For simplicity's sake, we'll assume an error on a TF always produces a negative for the factor being checked.

< snip >

So there's about a 1/(64*1,136,364) chance that the one computation error was during a factor, rendering a false negative. That's a 0.000001375% chance of a missed factor for every error your computer makes.

< snip >

Unless I'm making some false assumptions

There does seem to be an assumption there that a computation error would affect the checking of only one candidate factor.

What if there's a computation error affecting the increment between candidate factors or the screening-out of candidates divisible by small primes? Then one error could affect many candidates by causing large numbers of potential factors not to be tested. Up to a whole bit level -- zillions of candidates -- could be erroneously reported negative, when not a single candidate on that level was actually tested.

My guess is that there is much less chance that a single error systematically affects large numbers of candidates than that it affects only the test of a single candidate. But that smaller chance should be multiplied by the large number of candidates affected if it happens, to properly judge the impact.

[lfm]

I'd think the (slim) chance of accidental false negatives wouldn't warrant massive double checking. The subsequent LL test(s) will settle the matter of primality after all. Only if you're keen to find factors of known composites would it be of interest.

Also the P-1 and ECM searches seem to perform an implicit check for missed factors.

If there is systematic false negatives either a bug or fraud, they should show up in statistics I think since the odds of finding factors are fairly well known aren't they? If there's any statistical outliers by account or by program/version then rechecking a sampling might be warranted.