mersenneforum.org (https://www.mersenneforum.org/index.php)
-   -   Trial Factoring for Dummies (https://www.mersenneforum.org/showthread.php?t=25493)

 kriesel 2020-04-28 10:52

[QUOTE=R.D. Silverman;544044]So if two different machines trial divide with two different sets of trial factors how do you know whether a true factor was actually tested??? You might be missing some.[/QUOTE]It's my understanding that the leading gpu TF applications use not too few but too many candidate factors. Incomplete sieving of trial factoring candidates is accepted because it is higher performance, without excluding any candidate prime factors. It's faster in practice to sieve the Mersenne number with an occasional composite factor candidate also included, than to perfectly sieve the factor candidates. All the primes of the proper form in 2[SUP]b[/SUP] to 2[SUP]b+1[/SUP] are in the set of trial factors when doing TF from b to b+1, plus a varied set of composites. Assuming the hardware and software are operating to spec, that is, or sufficiently near it.

That's covered in points 8 and 9 of [URL]https://www.mersenneforum.org/showpost.php?p=508523&postcount=6[/URL] (my attempt to document all the concepts of mfaktc trial factoring I could identify, which had been reviewed by the author of mfaktc)

But suppose one in 10[SUP]6[/SUP] primes were omitted somehow from the TF candidate factors. We would still get nearly all the benefits of a perfect TF process, with all or nearly all the run time of a perfect TF process, over the same bit size interval.
A usable proof of work algorithm needs to be tolerant of both some level of expected software imperfection and speed optimizations.

 Prime95 2020-04-28 13:33

[QUOTE=R.D. Silverman;544044]So if two different machines trial divide with two different sets of trial factors how
do you know whether a true factor was actually tested??? You might be missing some.[/QUOTE]

All prime factors will be tested. A small non-deterministic set of composite factors will also be tested.

 chalsall 2020-04-28 13:52

[QUOTE=Prime95;544067]All prime factors will be tested. A small non-deterministic set of composite factors will also be tested.[/QUOTE]

Please forgive my ignorance, but would it be expensive to somehow sum/hash the vector of dividing candidates, post sieve? Or are they spread over too many vectors?

Edit: Sorry, I just realized this would be useless. Different for every run. Never mind...

Edit2: What about a sum/hash of the vector of candidates /before/ the sieve? Is that deterministic and reproducable? (Sorry... Haven't had my second cup of coffee yet...)

 kriesel 2020-04-28 15:55

[QUOTE=Prime95;544067]All prime factors will be tested. A small non-deterministic set of composite factors will also be tested.[/QUOTE]Hmm.
Is this non-deterministic set of composite factors a problem for Gerbicz' TF proof of work method? [URL]https://www.mersenneforum.org/showpost.php?p=509277&postcount=30[/URL] If for the set of q=2kp+1 that are composite but are not sieved out, one or more of (Mp mod q) mod 2[SUP]t[/SUP] is 1, it would seem so. Testing in that case that a candidate k for the proof list gives a prime q (finishing the sieving of only those that are candidates to go into the verification list) should handle that. Maybe that's best done on the cpu. The value of the list formed, as a proof of work, is that it is hard to produce, and easy to verify, rather like a found factor. Also it is usable in the most common TF case, no factor found. And depends on doing most of the actual TF work. And can be made reliable yet somewhat compact in size. And does not depend on keeping secrets such as encryption codes secret.

One of the reasons I like the Gerbicz double mod method is something analogous might be usable for P-1 verification of work, which is also not currently present. Some fraction of the code could be reused.

 chalsall 2020-04-28 18:03

[QUOTE=axn;544032]Because of variable SoE sieve depth (and the inherent nondeterminism in GPU sieve), the exact sequence of candidate factors produced can vary and so the server can't validate the residue.[/QUOTE]

Please forgive another possibly stupid question (I understand mfaktc largely as a black box)... But if the SieveP is constant during a run, does that make anything more usefully deterministic?

Probably wouldn't help determine sanity during runtime, but it would open the option of random DCs (for kit sanity checks, for example, if the user wanted to check and monitor their own kit).

 SethTro 2020-04-28 18:28

[QUOTE=axn;544032]You have clearly not done any GPU programming. What sounds like a simple operation in CPU land will have a large impact on GPU performance (not like 2x hit, but easily 20-30%). But for the sake of argument, let's say this is acceptable
[/QUOTE]

Luckily there are some GPU programmers here! I coded up [URL="https://www.mersenneforum.org/showpost.php?p=520512&postcount=199"]my proposal[/URL] and see less than a 5% performance impact (I measured 2-3% over 4 hours of work but with some margin of error)

[QUOTE=axn;544032]
The problem is that all of these have different authors. Any many people have their own scripts. Some people just manually get assignment from server and launch using command line. This isn't just code change -- it is a complex "system" change. The problem is that the whole "GPU TF" thing isn't very streamlined. Anyway, for the sake of argument, let's assume that this can somehow be coordinated.
[/QUOTE]

I asked about distribution somewhere and was told that mfaktc is ~30% of GPU factoring so starting there would be a good idea.

 kriesel 2020-04-28 18:52

[QUOTE=SethTro;544094]I asked about distribution somewhere and was told that mfaktc is ~30% of GPU factoring so starting there would be a good idea.[/QUOTE]Wow, I thought mfaktc was more than that, closer to 70%. As far as I know, there's only mfaktc, mfakto, and perhaps TJAOI. Mfakto competes for AMD gpus and their higher DP throughput relative to TF throughput with primality testing and P-1 with gpuowl. What are the other gpu TF apps for GIMPS? (I'm always looking for more for the "available software" list [URL]http://www.mersenneforum.org/showpost.php?p=488291&postcount=2[/URL])

 SethTro 2020-04-28 23:57

[QUOTE=kriesel;544099]Wow, I thought mfaktc was more than that, closer to 70%. As far as I know, there's only mfaktc, mfakto, and perhaps TJAOI. Mfakto competes for AMD gpus and their higher DP throughput relative to TF throughput with primality testing and P-1 with gpuowl. What are the other gpu TF apps for GIMPS? (I'm always looking for more for the "available software" list [URL]http://www.mersenneforum.org/showpost.php?p=488291&postcount=2[/URL])[/QUOTE]

I looked up the post that I had basing that number on and I have incorrectly recalled it as having a percentage which it doesn't.

 SethTro 2020-04-29 00:05

[QUOTE=axn;544055]Perhaps we should do some threat modeling before evaluating proposed solutions.

What is the current problem? Someone can fake a "no factor" result by manually typing up the result line and submitting to the server.

A simple checksum that can only be generated by the client should prevent that. It should have the property that different exponent/bit level should give unique value. Presumably, the client should have enough safeguards that it can't be tricked into computing the checksum without doing the actual work. This would mean encrypting the checkpoint files written to the disk.

I don't think for the problem as stated, we need proof of work. Provided the server trusts the client, the checksum is basically the client vouching for the work done -- that should be good enough.[/QUOTE]

I think this is a good line of reasoning.

A suspect some small percent of TF results were never run because manually created NO_FACTOR results including a larger bitrange were submitted (e.g. a NF result for bitrange 1-80). Making that harder (via a checksum for the line even) seems like a good starting place. If you want to do more to verify the calculating (to prevent against overclocking / math errors) we should look at my proof-of-work proposal.

 chalsall 2020-04-29 16:39

1 Attachment(s)
[QUOTE=retina;544054]Revised "kit": ALL of it. Everything that is required to run a test. Including the power cable, the OS, the drivers, and the ability to keep the kitty off the keyboard.[/QUOTE]

My problem is keeping the kittens off the bed... :smile:

 kriesel 2020-04-29 16:42

[QUOTE=chalsall;544197]My problem is keeping the kittens off the bed... :smile:[/QUOTE]I find doors work well. Although if it's the bedroom door, they'll hook it at the bottom with a paw and rattle it in the frame until "he who feeds cats" wakes up, so a more distant door is better.

All times are UTC. The time now is 22:59.