Agreed. Typical mathematician mentality People would be more convinced by presenting a factorization of a challenge RSA number
As a computational mathematician, I must object. The world is large enough for multiple deep specializations. I can't think at this level of abstraction (hence, I quit number theory after bashing at it for a few years). I can, however, read a math paper and put together an implementation as long as I'm familiar with the notation and the axiom of choice hasn't been used in a nontrivial matter. But then, my implementat…
In the 2020 preprint: "These new algorithms factor integers N ≈ 2^400 and N ≈ 2^800 using 7x10^10 and 4.3x10^12 arithmetic operations". He does not specify how many it uses for 2^1024 or 2^2048. This is clearly nonlinear. Assume (nevertheless) that you multiply x100 every 400 binary digits, then for 2^2048, you get (2048-800) equiv 1200/400 equiv 3, so you would need approx. 10^12*10^6 operations. Assuming you can do…
I'm getting 1e9 multiplication (2.5e8 div) ops per second in Node on a 2018 Macbook pro. So that would be 30 - 120 years. Not sure how well this algorithm can be parallelized, but since it's factoring, I think it can. So I would think that a dedicated attacker could get at least another 1000x on that, which gives 11-44 days. Note that I am pretty much guessing here but this is my test code:
function test(opp, n) {
const start = Date.now();
let i = 1;
if (opp === '*') {
let prod = 1;
while (i
In the 2020 preprint: "These new algorithms factor integers N ≈ 2^400 and N ≈ 2^800 using 7x10^10 and 4.3x10^12 arithmetic operations". He does not specify how many it uses for 2^1024 or 2^2048. This is clearly nonlinear. Assume (nevertheless) that you multiply x100 every 400 binary digits, then for 2^2048, you get (2048-800) equiv 1200/400 equiv 3, so you would need approx. 10^12*10^6 operations. Assuming you can do…
I'm getting 1e9 multiplication (2.5e8 div) ops per second in Node on a 2018 Macbook pro. So that would be 30 - 120 years. Not sure how well this algorithm can be parallelized, but since it's factoring, I think it can. So I would think that a dedicated attacker could get at least another 1000x on that, which gives 11-44 days. Note that I am pretty much guessing here but this is my test code: function test(opp, n) { co…
Guess: The "multiplications" we're talking about are those of 400-bit or 800-bit numbers (and, in general, would be the size of the number you're trying to factor), which are much more expensive than 64-bit x 64-bit or float x float multiplications. If you want to test the cost of that, I recommend GMPlib's bignums (or possibly just your favorite language that has built-in bignum support, although if it's not built on GMPlib it might not be using the most efficient algorithms).
I really hope this is not just another Atiyah moment. Sigh.
It is an Atiyah moment in the our response to this: both men earned the right to have those publications silently ignored, not being made into an attraction.
Without experimental data to back it up (e.g. implementation and benchmarks), I'd consider this claim veeeery dubious - regardless of who it came from. Extraordinary claims need extraordinary evidence, and in this case it would be easy to provide such evidence - by cracking appropriately-sized challenge primes in a transparent way that can be independently verified. On the other hand, the theoretical approach in the…
Depends of the claim.
For the theoretical result, the evidence is the paper. (I have no clue whether it’s correct.) Nothing else is needed.
For “RSA is broken”, it depends what broken means. If it would rely on a claim that is now provably false, it is indeed broken. If we are talking about the claim of breaking RSA in the real world, I agree with you. But it all depends on the claim.
I'm getting 1e9 multiplication (2.5e8 div) ops per second in Node on a 2018 Macbook pro. So that would be 30 - 120 years. Not sure how well this algorithm can be parallelized, but since it's factoring, I think it can. So I would think that a dedicated attacker could get at least another 1000x on that, which gives 11-44 days. Note that I am pretty much guessing here but this is my test code: function test(opp, n) { co…
Guess: The "multiplications" we're talking about are those of 400-bit or 800-bit numbers (and, in general, would be the size of the number you're trying to factor), which are much more expensive than 64-bit x 64-bit or float x float multiplications. If you want to test the cost of that, I recommend GMPlib's bignums (or possibly just your favorite language that has built-in bignum support, although if it's not built o…
Without experimental data to back it up (e.g. implementation and benchmarks), I'd consider this claim veeeery dubious - regardless of who it came from. Extraordinary claims need extraordinary evidence, and in this case it would be easy to provide such evidence - by cracking appropriately-sized challenge primes in a transparent way that can be independently verified. On the other hand, the theoretical approach in the…
"This giant prime number will keep your information totally unreadable to anyone who doesn't have this other giant prime number" is no less of an extraordinary claim, just one that we all believe in (myself included).
Way back when dinosaurs roamed the earth and comp.compression on Usenet was a place to be, usually we went beyond the pigeonhole principle by asking people to grab a megabyte from random.org, compress it, and then get back to us. Nobody ever did.
I remember one of those exchanges, two people waged money about compressing random data so that the data + decompress program would be smaller than the original data. The other guy came back with a program that moved some of the random data into the metadata of the filesystem, in such a way so that the produced files did indeed become small enough. Don't know if the other guy ever paid out.
I think I remember that one too, or definitely one like it.
That's a cheap trick. You gotta send someone the file, otherwise there's not much of a point.