5 ms·

It's strange that the authors pick integer factorization as the problem to solve on their machine. Although their machine may provide a speedup for optimization

It's strange that the authors pick integer factorization as the problem to solve on their machine. Although their machine may provide a speedup for optimization problems, these speedups are not relevant for the problem of integer factorization, as shown in https://arxiv.org/abs/1902.01448 https://arxiv.org/abs/1902.01448 (disclaimer: I am a co-author of that paper). Skimming over the paper it seems their method of translating factorization to the optimization problem consists of simplifying equations without justification that this can be done efficiently. I suspect that their preprocessing step is already NP-hard. The second and more important issue, is that the overall strategy---of translating a problem with a sub-exponential classical complexity (via the Number Field Sieve) to an optimization problem with exponential runtime---is not expected to succeed, as confirmed by careful measurements in our paper.

sokrates85 7y ago
I agree that the integer factorization is a poor choice. Last statement in the Abstract talks about sampling and optimization which could be the bigger point. Their pre-processing seems like simply expanding out their cost function that's of the form E= (F - XY)^2. Of course it's a lot of multiplications since X and Y are binary and multi-dimensional. Not sure if it would be NP-hard though.
bike4beer 7y ago
Well this is the problem that's going to get NSA's attention, this is the problem where the money is, .... So why not show this problem? 1.) poor mans qubit aka pbit, check :) 2.) room temp, no cryogenics, check :) 3.) any 3rd world kid can hack an mram and bust bitcoin NSA's edcsa-256pk1 and sha256 :) What's not to like? Well it scale? Who cares, the cat is out of the bag. Entanglement, that's easy. I worked on this problem a few years ago ( redeployed my GPU mining racks to do 100's of billions of 256bit multiplys per second ), there are 10E5 valuable bitcoins, but 10E72 candidates, we're talking number of atoms in universe, and more than likely when you crack one, its most likely to have no value I can see a lot of value in this technique as the biggest problem is generating random candidates to factor using advanced methods. A method of probabilistic keeping you in the ball park is far better than brute force. ( generating random private key ball-park candidates is the most critical in finding keys ) Again, the problem isn't factoring, the problem is factoring high-value keys Using this method to keep you in the 10E5 window of high-value targets sound like a great technique.

sokrates85 7y ago

I agree that the integer factorization is a poor choice. Last statement in the Abstract talks about sampling and optimization which could be the bigger point. Their pre-processing seems like simply expanding out their cost function that's of the form E= (F - XY)^2. Of course it's a lot of multiplications since X and Y are binary and multi-dimensional. Not sure if it would be NP-hard though.

bike4beer 7y ago

Well this is the problem that's going to get NSA's attention, this is the problem where the money is, .... So why not show this problem? 1.) poor mans qubit aka pbit, check :) 2.) room temp, no cryogenics, check :) 3.) any 3rd world kid can hack an mram and bust bitcoin NSA's edcsa-256pk1 and sha256 :) What's not to like? Well it scale? Who cares, the cat is out of the bag. Entanglement, that's easy. I worked on this problem a few years ago ( redeployed my GPU mining racks to do 100's of billions of 256bit multiplys per second ), there are 10E5 valuable bitcoins, but 10E72 candidates, we're talking number of atoms in universe, and more than likely when you crack one, its most likely to have no value I can see a lot of value in this technique as the biggest problem is generating random candidates to factor using advanced methods. A method of probabilistic keeping you in the ball park is far better than brute force. ( generating random private key ball-park candidates is the most critical in finding keys ) Again, the problem isn't factoring, the problem is factoring high-value keys Using this method to keep you in the 10E5 window of high-value targets sound like a great technique.