mersenneforum.org Trial Factoring for Dummies
 User Name Remember Me? Password
 Register FAQ Search Today's Posts Mark Forums Read

2020-04-28, 10:52   #34
kriesel

"TF79LL86GIMPS96gpu17"
Mar 2017
US midwest

4,423 Posts

Quote:
 Originally Posted by R.D. Silverman 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.
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 2b to 2b+1 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 https://www.mersenneforum.org/showpo...23&postcount=6 (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 106 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.

Last fiddled with by kriesel on 2020-04-28 at 11:01

2020-04-28, 13:33   #35
Prime95
P90 years forever!

Aug 2002
Yeehaw, FL

715510 Posts

Quote:
 Originally Posted by R.D. Silverman 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.
All prime factors will be tested. A small non-deterministic set of composite factors will also be tested.

2020-04-28, 13:52   #36
chalsall
If I May

"Chris Halsall"
Sep 2002

67·139 Posts

Quote:
 Originally Posted by Prime95 All prime factors will be tested. A small non-deterministic set of composite factors will also be tested.
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...)

Last fiddled with by chalsall on 2020-04-28 at 13:55

2020-04-28, 15:55   #37
kriesel

"TF79LL86GIMPS96gpu17"
Mar 2017
US midwest

4,423 Posts

Quote:
 Originally Posted by Prime95 All prime factors will be tested. A small non-deterministic set of composite factors will also be tested.
Hmm.
Is this non-deterministic set of composite factors a problem for Gerbicz' TF proof of work method? https://www.mersenneforum.org/showpo...7&postcount=30 If for the set of q=2kp+1 that are composite but are not sieved out, one or more of (Mp mod q) mod 2t 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.

Last fiddled with by kriesel on 2020-04-28 at 16:25

2020-04-28, 18:03   #38
chalsall
If I May

"Chris Halsall"
Sep 2002

67·139 Posts

Quote:
 Originally Posted by axn 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.
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).

2020-04-28, 18:28   #39
SethTro

"Seth"
Apr 2019

2×34 Posts

Quote:
 Originally Posted by axn 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
Luckily there are some GPU programmers here! I coded up my proposal and see less than a 5% performance impact (I measured 2-3% over 4 hours of work but with some margin of error)

Quote:
 Originally Posted by axn 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.
I asked about distribution somewhere and was told that mfaktc is ~30% of GPU factoring so starting there would be a good idea.

2020-04-28, 18:52   #40
kriesel

"TF79LL86GIMPS96gpu17"
Mar 2017
US midwest

4,423 Posts

Quote:
 Originally Posted by SethTro I asked about distribution somewhere and was told that mfaktc is ~30% of GPU factoring so starting there would be a good idea.
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 http://www.mersenneforum.org/showpos...91&postcount=2)

2020-04-28, 23:57   #41
SethTro

"Seth"
Apr 2019

2·34 Posts

Quote:
 Originally Posted by kriesel 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 http://www.mersenneforum.org/showpos...91&postcount=2)
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.

2020-04-29, 00:05   #42
SethTro

"Seth"
Apr 2019

A216 Posts

Quote:
 Originally Posted by axn 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.
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.

2020-04-29, 16:39   #43
chalsall
If I May

"Chris Halsall"
Sep 2002

931310 Posts

Quote:
 Originally Posted by retina 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.
My problem is keeping the kittens off the bed...
Attached Thumbnails

2020-04-29, 16:42   #44
kriesel

"TF79LL86GIMPS96gpu17"
Mar 2017
US midwest

4,423 Posts

Quote:
 Originally Posted by chalsall My problem is keeping the kittens off the bed...
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.

 Similar Threads Thread Thread Starter Forum Replies Last Post garo GPU Computing 100 2019-04-22 10:58 NBtarheel_33 GPU Computing 10 2011-10-13 00:04 odin Software 4 2010-08-08 20:23 S485122 PrimeNet 1 2007-09-06 00:52 jocelynl Math 8 2006-02-01 14:12

All times are UTC. The time now is 17:09.

Thu Sep 24 17:09:09 UTC 2020 up 14 days, 14:20, 1 user, load averages: 1.87, 1.88, 1.72