# 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"?

-
Why not select the primes yourself and create a challenge using that? That way it would be trivial for you to verify if there is (at least) a prime falling inside a given range. Or is this a distributed proof of work scheme? –  Thomas Jun 29 '13 at 8:46
What is the actual problem you're trying to solve? Sounds like an XY problem. Checking if a number is prime is fast (no need to distribute), for factoring there are much faster algorithms than trial divisions and as proof of work this isn't better than partial hash pre-images. So what's the point? –  CodesInChaos Jun 29 '13 at 8:47
@Thomas It is a distributed proof of work scheme. I am thinking about distributing people checking whether a really big number has divisors in specified range. –  ThePiachu Jun 29 '13 at 8:55
@ThePiachu Trial division only works on really small primes since it's cost is exponential in the length of the prime ($2^{n/2}$ trial divisions for an $n$ bit prime). So it scales perhaps up to 160 bits with a lot of work. Good primality tests have polynomial runtime, something like $n^4$. Please read Primality test on wikipedia –  CodesInChaos Jun 29 '13 at 9:22
I don't see how a proof of work would help in that. $\:$ I doubt that there is a known coNTIME algorithm for your problem whose proofs can be found faster than factoring, although there might be an efficient way to make the computation verifiable. $\;\;\;$ –  Ricky Demer Jun 29 '13 at 9:53

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.

-