Today ASICs can easily calculate SHA-256 for bitcoin mining. As an alternative proof of work (PoW) the miners can be given the problem of solving integer factorization. This type of PoW can perhaps make CPUs more competitive versus ASICs.
"In number theory, the prime factors of a positive integer are the prime numbers that divide that integer exactly.[1] The prime factorization of a positive integer is a list of the integer's prime factors, together with their multiplicities; the process of determining these factors is called integer factorization. The fundamental theorem of arithmetic says that every positive integer has a single unique prime factorization.[2]" --
http://en.wikipedia.org/wiki/Prime_factorEach Bitcoin block is hashed to a very large integer
N. And the task is to calculate a large enough number of integer factors for
N to reach a target
d. The difficulty is made variable by requiring different numbers of factors
d in the solution. Notice here that the factors can be other integers than primes.
This is a different method than ordinary prime factorization. The miners provide a solution
S which is a list that contains at least
d factors (len(
S) >=
d). The solution is verified by multiplying all the factors in
S and checking if the product equals
N (
∏si =
N).
If the
prime factorization of
N results in less factors than
d, then that's a valid solution. When
S contains less factors than
d then the validation must also do a primality test on the factors to check if they are all primes. "Factorization is thought to be a computationally difficult problem, whereas primality testing is comparatively easy (its running time is polynomial in the size of the input)." --
http://en.wikipedia.org/wiki/Primality_testExample:
N = 48
d = 3
S = [2, 2, 12]
Another example:
N = 123
d = 3
S = [3, 41]
In the second example, S is the prime factorization of N.
The value N is calculated as a hash value of the Bitcoin block in a way that makes factorization hard.
