Quantum Supremacy — Factoring Large Primes

[catsmate]

What would really blow my mind?
Factoring complex numbers like quaternions.


P. S. Obligatory math joke:

Q: How do you solve the Ramen Hypothesis?
A: Use your big noodle.

It would impress me if people understood the difference between 'prime number' and 'prime factor'...

 

[Blue Mountain]

You mean "product" where you said "sum".

Indeed I did.

 

[smartcooky]

Being able to factor the product of two large primes in a reasonable amount of time would allow you to break the RSA cryptosystem and some similar cryptosystems. That is one of the main reasons why the US government is so interested in funding quantum computing.

For perspective: 1,099,551,473,989 is roughly 40 bits. These days, RSA keys are usually at least 1024 bits, or as many as 4096 bits.

Setec Astronomy.

 

[Robin]

Even that doesn't require a quantum computer. To generate a list of primes from 2 to (say) 2,000,000 could be done on an ordinary PC in no time.



Using LISP, factorizing 1099551473989 is also a quick operation.

I remember when it was a big deal for a quantum computer to find the prime factors of 21. The significance lies in being able to do it at all with a quantum computer. Some people were saying we would never reach 91 with a quantum computer.

 

[Darat]

All this research so they can charge more for selling adverts.

 

[Robin]

Any company that could bust RSA encryption and hold patents on the next generation of quantum encryption would be able to charge for a lot more than just advertisements.

 

[caveman1917]

Busting RSA encryption wouldn't be the end of the world though, there are other encryption schemes based on for example elliptic curves for which no faster quantum algorithm exists. Sure, the world would have to move away from RSA encryption but it's not like alternatives aren't available.

 

[theprestige]

Moving away from RSA would be a pain in the ass, though.

 

[Robin]

Moving away from RSA would be a pain in the ass, though.

Moreover it would be a huge cost if it had to be done too rapidly, it could easily cause a large economic downturn.

 

[caveman1917]

Busting RSA encryption wouldn't be the end of the world though, there are other encryption schemes based on for example elliptic curves for which no faster quantum algorithm exists. Sure, the world would have to move away from RSA encryption but it's not like alternatives aren't available.

Minor correction, it appears that only some particular key-exchange algorithms based on elliptic curves are quantum-proof but the general elliptic curve based encryption schemes are equally vulnerable as RSA. There are still plenty of quantum-proof encryption schemes though.

 

[Hellbound]

Moving away from RSA would be a pain in the ass, though.

It's already in progress, though; at least for TLS. While RSA is still in use, it's a minority of the allowed ciphers in NIST's TLS guidelines now. Check NIST SP 800-52r2, Section 3.3.1 (https://nvlpubs.nist.gov/nistpubs/SpecialPublications/NIST.SP.800-52r2.pdf). A LOT more ECDSA, DSA, DH, and ECDH as the recommendations now. A lot of the public certificate providers are issuing ECDHE certs now as well. RSA is still present, but that move is already starting.

I can't speak much outside TLS, though, so you may have more insight in that area (TLS is primarily what I deal with).