Proof of work for determining whether a number is prime? I have an idea for a system that would be outsourcing some brute force calculations to many users in hopes of finding divisors of a number. However, there is a possibility that a given number would be prime, or that it would not have a divisor in a given range.

For example, a computer might be tasked to look for a divisor of a number 2^n-1 (which would be a very large number) and whether there is a divisor in range x*10^10 to (x+1)*10^10.

Proving that one has found a divisor is easy - they just need to submit that divisor and the number can be checked against it. However, how should the users go about proving that there is no divisor to be found in a given range? Obviously one couldn't just trust a user in their claims - this would open a possibility for malicious reports messing with the system.

So far I was pondering a few options - submitting overlapping regions to various users for checking and comparing their results, challenging the users to find the smallest / biggest remainder of a check they would be performing in the range and so forth. Are there any approaches to the presented problem that are more vetted in the crypto world than "an idea that sounds okay"?
First off: Divisibility testing is an atrociously bad way to check whether a number is prime or not.  It is horribly inefficient and ineffective.  You need to first read up on the literature on primality testing before you think about how to distribute it among untrusted clients.

Use any standard primality test.  Give each client a different iteration of the test, and have them send you the result.

For instance, you could use Miller-Rabin primality testing.  The idea of this primality test is that you choose a random value $a$, then do some computation based upon $a$ (e.g., you compute $a^d \bmod n$, and some other stuff that I'll ignore for simplicity); this might result in a proof that $n$ is not prime, or it might result in nothing.  If you do this 10 times with 10 different random values $a$, and none of them find a proof, then it's very likely that $n$ is prime.

Here's how you could distribute Miller-Rabin primality testing:


Choose a few dozen clients randomly.
For each client, pick the value $a$ randomly.  Give the client $a$.  Ask the client to compute $a^d \bmod n$ and send it back to you.
If any client claims to have found a proof that $n$ is not prime, send the same $a$ to 4 other randomly chosen clients.  If at least 3 out of those 5 clients give you the same value for $a^d \bmod n$, then probably all 3 of those were honest and probably $n$ is not actually prime.
If none of the clients found a proof of non-primality, then probably $n$ is prime.
If you ever want to confirm that a particular client did its work correctly, send the same value $a$ to a few other clients and see if they all return the same value for $a^d \bmod n$.


You can adjust the parameters (the number of clients selected, the number you require to agree before you accept the result is probably correct, the number of iterations of Miller-Rabin) based upon how much confidence you require and what fraction of your clients you think are honest.

I expect this framework ought to lead to an efficient way to test primality of even very large numbers.  If it doesn't suffice in your setting, then you should edit your question to provide more specifics of why it does not work and what you have tried.