Integer Factorization as PoW in a Blockchain

[retina]

Factoring random numbers doesn't give answers anyone cares about. The numbers themselves, or their factors, have no value.

The only potential upside is to encourage people to develop better/faster/easier/whateverer factoring methods that can then be applied to other numbers that are interesting.

But I don't see it ever happening. The greedy folks doing blockchain coins stuff are not likely to be mathematicians. And the mathematicians doing the real factoring advancement work aren't likely to care about, or be motivated by, blockchain coin needs.

But no matter, it's your electricity bill to pay, not mine.

I think I should start a power generation company and then promote blockchain coins as being the saviour of humanity.

[charybdis]

Originally Posted by retina

But I don't see it ever happening. The greedy folks doing blockchain coins stuff are not likely to be mathematicians. And the mathematicians doing the real factoring advancement work aren't likely to care about, or be motivated by, blockchain coin needs.

Personally I think that if blockchain-factoring becomes big then improvements are most likely to be technological - that is, the development of ASICs for lattice sieving and block Lanczos/Wiedemann - rather than algorithmic. Partly because, as you say, the interests align more. I wouldn't be surprised if the NSA etc already have such ASICs.

[a1call]

Originally Posted by factorn

Correct. The miner's job is to find semiprimes by way of factoring/sieving within some parameters rather than factoring a given semiprime or simply generating a semiprime.

Thank you factorn for the enlightenment/clarification.
As for interest in performing the mining, it is no worse that what Bitcoin miners achieve/contribute.
One thing that is probably undeniable is that not being the 1st in IT related endeavors is a major roadblock.
Very many high school graduates can write codes which can mimic/surpass the mechanics of say Wikipedia, Twitter or Bitcoin and many already have, but somehow they can never move beyond being the underdog regardless of how much better they may be. Not quite sure why.
Perhaps google has to tweak its algo to allow the rivals land the 1st search spot once in a while rather than giving the across-the-board monopoly to Wikipedia.
Ok google, did you hear that? I’m sure you did.

[factorn]

@chalsall

The more I read people's questions, and the answers you (sometimes) give, the less and less I think your idea will ever be useful. To anyone.

The deadpool will allow you and anyone else to submit numbers to be factored to the blockchain by a FACT coin fee. Given what I have seen on this forum already, there is a market for such a thing. Blockchain technology adds a financial incentive for people to do it.

Also, it is not useful to get emotional when defending an idea. Particularly when more and more holes are pointed out in said idea.

I agree.


@retina

Factoring random numbers doesn't give answers anyone cares about. The numbers themselves, or their factors, have no value.

Before you can a deadpool to allow you to submit numbers that are of interest to factorization you must first have a blockchain to begin with. And even more powerful, have a blockchain where the PoW is factoring.

The only potential upside is to encourage people to develop better/faster/easier/whateverer factoring methods that can then be applied to other numbers that are interesting.

Well, yes.

But I don't see it ever happening. The greedy folks doing blockchain coins stuff are not likely to be mathematicians.

I do not share this view. In particular, I am a mathematician...I developed this blockchain. Counter example 1. I can actually point to others, but let's not name names.

And the mathematicians doing the real factoring advancement work aren't likely to care about, or be motivated by, blockchain coin needs.

True though this may be, should this blockchain become financially viable it will literally fund their efforts. It takes all types. The mathematical community has a strong self-interest in promoting endeavors that advance knowledge and research, and if there appears an opportunity where greedy blockchain people and financial interests align with the mathematicians, and they want to help mathematicians develop better mathematical theory for their own selfish reasons......why should the mathematical community reject this? This sounds like synergy to me and a win-win situation.


I do recommend you read the whitepaper: https://fact0rn.io


@charybdis

Personally I think that if blockchain-factoring becomes big then improvements are most likely to be technological - that is, the development of ASICs for lattice sieving and block Lanczos/Wiedemann - rather than algorithmic.

I strongly disagree. From a business perspective if you are going to invest 1 million dollar into mining FACT0RN coin and there is a nontrivial probability that some researcher in his basement can come up with a factoring algorithm that is better than NFS to factor, or even gain a 10% advantage using some new trick within NFS, the businessman will hedge against this by having his own group of researchers or a community of such researchers working this problem. Otherwise, he is exposing himself to unnecessary risk on his investment.



@a1call: you are welcomed.

Very many high school graduates can write codes which can mimic/surpass the mechanics of say Wikipedia, Twitter or Bitcoin and many already have, but somehow they can never move beyond being the underdog regardless of how much better they may be. Not quite sure why.

The utility of FACT0RN coin beyond measuring progress in factoring "technology", accelerating advancements in knowledge/theory/implementations of factoring is that the deadpool allows you to ask folks who are financially motivated to factor to offer factoring as a service through the blockchain. If there is a market for such a thing then FACT0RN will grow just fine.

[charybdis]

Originally Posted by factorn

@charybdis
I strongly disagree. From a business perspective if you are going to invest 1 million dollar into mining FACT0RN coin and there is a nontrivial probability that some researcher in his basement can come up with a factoring algorithm that is better than NFS to factor, or even gain a 10% advantage using some new trick within NFS, the businessman will hedge against this by having his own group of researchers or a community of such researchers working this problem. Otherwise, he is exposing himself to unnecessary risk on his investment.

But surely by the same argument the business should hire engineers to design and build ASICs? Okay, it's not researchers in their basements (lol, who does their research in their basement?) but other businesses that are the worry here, but that's still a risk that one should hedge against. Plus it would counter the risk of a small improvement to NFS that you mention. And at least in my opinion working ASICs for NFS are more likely than a faster-than-NFS algorithm.

[chalsall]

Originally Posted by factorn

@chalsall The deadpool will allow you and anyone else to submit numbers to be factored to the blockchain by a FACT coin fee. Given what I have seen on this forum already, there is a market for such a thing. Blockchain technology adds a financial incentive for people to do it.

Again, I (and many) don't think your idea will work. At _best_ it *might* be able to maintain a chain by finding factors that no one cares about. This eliminates your "market".

But, just as a thought experiment...

Could you please give me the exact process that would be involved in submitting 2^1277-1 to be factored? We already know it's composite, but we don't (yet) know any factors. How would the "cost" be determined?

This also brings up the question of how you will be dealing with Candidates of a special form.

[factorn]

@charybdis

But surely by the same argument the business should hire engineers to design and build ASICs?

Correct.

And at least in my opinion working ASICs for NFS are more likely than a faster-than-NFS algorithm.

ASICS will certainly be a thing. Simultaneously, faster-than-NFS is a real posibility. It is not an either-or situation.


@chalsall

Could you please give me the exact process that would be involved in submitting 2^1277-1 to be factored?

Numbers of a special form, say a*b^c+d, can be added to the deadpool feature. So instead of submitting the number, you submit a,b,c,d along with the special form to which it refers to, and this would take very little space on the blockchain. The answer might be "very long" as far numbers go and not have a special form, but the blockchain charges per kylobytes in the transaction so that cost is built in as far as storage.

We already know it's composite, but we don't (yet) know any factors. How would the "cost" be determined?

The coins paid to this problem in the deadpool will be rewarded to anyone who finds ANY non-trivial factor of this number. Mind you, if you submit a prime, your coins will be locked forever. The cost for the job will be a constant value, a minimum, that will be relatively close to the transaction cost of the blockchain, very likely 10x-100x of a transaction cost. From there the market takes over, if no one wants to factor that number for the reward offered you can always add more reward for that job on the deadpool -- anyone, from any wallet, can add more. So, if other people are interested they can add coins to YOUR number in the deadpool.

This also brings up the question of how you will be dealing with Candidates of a special form.

At this point, this is just simple software engineering to handle special forms, but support for them can be added as they come up. A simple system to have a set of special forms of interest can be created and implemented. This is not really big deal.

[charybdis]

Originally Posted by factorn

ASICS will certainly be a thing. Simultaneously, faster-than-NFS is a real posibility. It is not an either-or situation.

Where did I say it was?
In fact, you seem to have implicitly acknowledged my earlier claim that ASICs would be a more likely development for blockchain-factoring than new algorithms, by your use of language ("certainly" vs "real possibility").

As I understand it, the reason we don't already have ASICs for NFS is that no-one has been willing to provide the large-scale investments that would be needed, and for good reason, because it wouldn't be profitable. Blockchain factoring would change that. On the other hand, number theorists do not need millions of $$ of support to work on discovering new factoring algorithms, so such research has been ongoing since the development of NFS 30 years ago... and as you know, all we've got is small incremental improvements to NFS. What this tells me is that developing a faster-than-NFS algorithm is difficult - after all, we have no proof that such an algorithm exists! - and there is no guarantee that throwing huge sums of money at funding research in this area will be successful.

[chris2be8]

Interesting numbers like 2^1277-1 are *much* harder than the numbers you are proposing as challenges. So it would need a *lot* of coins in the deadpool to make it worth factoring.

A more practical design for factoring interesting numbers would ask people to earn coins by sieving NFS relations for the current challenge (probably a job that would otherwise go on the 16e queue). Although this would need a completely different blockchain design.

Finding someone to solve that matrix once we had enough relations would be another issue. Though probably not a show-stopper.

[factorn]

@charybdis

Where did I say it was?
In fact, you seem to have implicitly acknowledged my earlier claim that ASICs would be a more likely development for blockchain-factoring than new algorithms, by your use of language ("certainly" vs "real possibility").

Again, it is not an either-or situation. They both have posibilities, ASICs are likely to happen sooner, but do not exclude faster-than-NFS algorithm discoveries.

As I understand it, the reason we don't already have ASICs for NFS is that no-one has been willing to provide the large-scale investments that would be needed, and for good reason, because it wouldn't be profitable. Blockchain factoring would change that.

Correct.

What this tells me is that developing a faster-than-NFS algorithm is difficult - after all, we have no proof that such an algorithm exists!

Nor do we have proofs that such algorithms do not exist.

and there is no guarantee that throwing huge sums of money at funding research in this area will be successful.

It would certainly accelerate the discovery process.



@chris2be8

Interesting numbers like 2^1277-1 are *much* harder than the numbers you are proposing as challenges. So it would need a *lot* of coins in the deadpool to make it worth factoring.

This is what a market does, it finds the right price for it. If that price happens to be a lot of coins, then that's what it is.

A more practical design for factoring interesting numbers would ask people to earn coins by sieving NFS relations for the current challenge (probably a job that would otherwise go on the 16e queue). Although this would need a completely different blockchain design.

Funny you should mention this. The original blockchain had a partial-work mechanism to allow for exactly this. You don't need a new blockchain. I decided not to include this one because it is wise to walk before running. But, this feature is coming. It does need be thought out more deeply though, and it does need a more expertise than I currently posses to work out some technical details that come up. But, I will submit a proposal for that feature after the blockchain is running and we have the deadpool implemented and working.

Finding someone to solve that matrix once we had enough relations would be another issue. Though probably not a show-stopper.

Correct. We can come up with a way to do this.

[a1call]

Just in case you did not know, there are ready made solutions for such market place. You can access them by googling the phrase:
Reverse Auction Software

ETA You might also want to google the phrase
Factoring Services
and research why there are no explicit such Integer related services available already, even though the tools for it have been available for years. I do not know myself but suspect there might be legal reasons.