**EDIT:
Quantum computing calculations have been updated and are now correct.
Also at the bottom points #2 and #3 have been made to address concerns
that the largest mining pool would always win since there is much less
random luck in getting proper factors as opposed to current finding the
nonce of the hash...meaning that cooperation in this idea would increase
the speed of finding the block above that of simple competition.
Currently in cryptocurrencies competition is just as fast as cooperation
(at least so we think).**

Some of
you may be afraid of Quantum Computers being an ASIC on CPU mining.
This post isn't about this topic but I will address it first.

The Monero blockchain can currently factor a 745 bit number in 2 minutes (approx).

According to this post
a 745 bit number needs 1492 (2n+2) clean logical qubits (which are very
hard to achieve, each qubit is exponentially harder to add than the
last) and would take around 2 trillion T gates. Looking at the history of quantum computers,
this is probably decades off imo, quantum computers can only run for a
few microseconds currently as well. By the time we get there the monero
blockchain can probably beat it. A million or so noisy qubits might be more practical and also at least decades off of course.

Here
is what I believe to be the Holy Grail to Mining and also I will
present some alternatives to this which will have a more precisely
adjustable difficulty but I don't think that is needed.

Factoring a large number over 100 digits is well known to not benefit significantly from parallelization
such as GPU's, FPGA's, and ASIC's. As I explained above, quantum
computers are also out of the running for the foreseeable future. The
cool thing about this is that there can be moderate speedup by
piggybacking a GPU and CPU since the GPU can support the General Number
Field Sieve (GNFS) function of the CPU. This is extra beneficial since
consumer hardware always has at least one of each but specialized chips,
including IoT device botnets do not.

To
implement this in Monero we would start with roughly 745 bits which is
225 decimal digits which would currently take about 1.9 minutes on the
monero blockchain. If we bumped that up to 226 digits or 748 bits, this
would take around 2.1 minutes. So I think this method is just fine in
how precise difficulty adjustment will be by just changing the number of
digits we are factoring. If we wanted more precision we could try to
factor numbers in binary which would give about 5x more precision on
difficulty adjustments. I will outline an even more precise possibility
at the end of this post.

So the
idea is this. We present a 225 digit (adjustable) number to the monero
blockchain. The first person (miner) to present the prime factorization
of that number wins the block. It is just about that simple. In order
to prevent really fast blocks for numbers that happened to be prime or
near prime, we can require that any answer to win a block must not
contain any factors larger than 113 digits (225/2). This requirement
just means that no "really easy" to factor numbers slip in. If an
answer is presented to the blockchain that contains prime factors larger
than this limit, then a new number is hashed for everyone to work on
(this is a point of potential abuse since if a miner finds that the
factorization doesn't meet the requirements he could work on the next
hash before releasing that info to the public. Somehow we would need to
figure out how to prevent this (**EDIT point #2 at the bottom of this
post addresses it**). To generate a number we can use Skein-1024 (or
SHA-1024) and truncate to the amount of digits we need.

I think that is pretty much it.

PRO's:

Asic, Gpu, FPGA Safe and as Quantum resistant as you can hope for, I say we cross that quantum bridge when we get there.

Simple easy to understand basic concept that has proven itself over decades of research to favor CPU.

Even
more favorable is 1 GPU + 1 CPU = 1 Vote which will help disincentivize
botnets and crazy big CPU's and favor APU's which are the current
consumer standard (or a enthusiast CPU plus an enthusiast GPU).

miner design will contain no surprises since GNFS programs have been written for decades both for CPU and CPU/GPU combo

CON's:

Very different from what we are used to which are cryptographic hashing functions.

Mining software would have to be developed, as well as the code of the PoW will need to be written from scratch.

Difficulty adjustment will be not quite so easy or precise and will require new difficulty adjustment algorithms.

Let me know your input on this idea and if you agree it could be a PoW that lasts monero decades instead of months.

-----

To
get even more difficulty adjustability we could use larger numbers and
just require one or more factors to be presented, not prime factors. So
say we ask for one 113 digit long factor of a 300 digit number. The
length of the number and the length of the factor required can be both
adjusted. Also the number of factors could be changed too. So to raise
difficulty of this very slightly we could require both a 100 digit
factor and a 113 digit long factor of a 300 digit number. since we
aren't looking for prime factors in this version, almost every number
will have at least one potential factor of these sizes. But still this
version should need GNFS sieve and trial division would take much much
much longer.

Another
possibility is releasing 10 or more numbers at a time and as soon as
any single number gets factored, then all 10 expire and the block is
won. This will allow mining groups to "audit" the numbers and select
one that will complete the requirements (no factors larger than 1/2 of
the bit number size). Also there is more random chance that one number
of the bunch could be factored faster negating the "largest mining pool
always wins" issue brought up in the comments by sech1.

Another
option is turning the coin code into one large pool that delegates
sub-tasks to individual pools or miners. This would also be a method to
address the concerns brought up by sech1.

Potential starts for mining software:

https://web.archive.org/web/20180320172551/http://gilchrist.ca/jeff/factoring/index.html

https://sourceforge.net/projects/msieve/files/?source=navbar

https://mersenneforum.org/showpost.php?p=294403&postcount=13