3 ms·

I'm not a mathematician, so excuse my ignorance, but is it wrong to call it factoring? The definition of a prime number is a number whose only factors are 1 and

I'm not a mathematician, so excuse my ignorance, but is it wrong to call it factoring? The definition of a prime number is a number whose only factors are 1 and itself, so you're still factoring the number to see if it fits the definition.

beisner 9y ago
The real threat of quantum computers is not the testing of prime numbers, but the factoring of semiprime numbers (numbers that have two distinct prime factors). The difficulty of taking a semiprime number and extracting it’s prime factors is considered an extremely hard problem, and this assumption of difficulty underpins nearly all of our modern cryptographic systems. If it were trivial to factor a large semiprime, one could intercept/hack all credit card transactions. This is the quintessential problem that quantum supremacy raises, and the most publicized; OP was remarking that the journalists likely meant to talk about this threat, but somewhat sloppily wrote prime instead of semiprime.
- ianai 9y ago
  The lay audience might ignore semi-prime and just interpret it as prime. Or the author did that.
- deleted 9y ago
  [deleted]
- AndrewGaspar 9y ago
  Oh, I see! Thank you for the explanation!
aiCeivi9 9y ago
People are interested in factoring numbers in context of breaking RSA encryption, so they knew factored number is not a prime. Also quantum algorithms are probabilistic so getting "it is a prime result" isn't very trustworthy. When we get actual factors it is easy to verify that with division/multiplication on classical CPU.
- bdamm 9y ago
  Indeed; while Quantum compute is an exciting development, I am suspicious of the conclusion that cracking classic crypto is just around the corner. There are enormous challenges yet to solve; reducing noise in the results down to a useful collection is just one. If the quantum computer gives you a correct result 1/2^64 times, or a result within range of the actual result to within 2^64 values, then it is far from complete doom for classical cryptography. It's very useful for lots of other things, so undoubtedly we'll see plenty of gains in in quantum applications.
  - lurquer 9y ago
    In the early 90's Ghandi got hold of one of these devices and caused havoc. Luckily, he was stopped by Bob Woodward with some help from Elwood Blues and, of course, President Roslin. I'd like to see Qbert crack that.
kilotaras 9y ago
You don't need quantum computers for primality tests. https://en.wikipedia.org/wiki/Primality_test https://en.wikipedia.org/wiki/Primality_test

beisner 9y ago

The real threat of quantum computers is not the testing of prime numbers, but the factoring of semiprime numbers (numbers that have two distinct prime factors). The difficulty of taking a semiprime number and extracting it’s prime factors is considered an extremely hard problem, and this assumption of difficulty underpins nearly all of our modern cryptographic systems. If it were trivial to factor a large semiprime, one could intercept/hack all credit card transactions. This is the quintessential problem that quantum supremacy raises, and the most publicized; OP was remarking that the journalists likely meant to talk about this threat, but somewhat sloppily wrote prime instead of semiprime.

ianai 9y ago
The lay audience might ignore semi-prime and just interpret it as prime. Or the author did that.
deleted 9y ago
[deleted]
AndrewGaspar 9y ago
Oh, I see! Thank you for the explanation!

aiCeivi9 9y ago

People are interested in factoring numbers in context of breaking RSA encryption, so they knew factored number is not a prime. Also quantum algorithms are probabilistic so getting "it is a prime result" isn't very trustworthy. When we get actual factors it is easy to verify that with division/multiplication on classical CPU.

bdamm 9y ago
Indeed; while Quantum compute is an exciting development, I am suspicious of the conclusion that cracking classic crypto is just around the corner. There are enormous challenges yet to solve; reducing noise in the results down to a useful collection is just one. If the quantum computer gives you a correct result 1/2^64 times, or a result within range of the actual result to within 2^64 values, then it is far from complete doom for classical cryptography. It's very useful for lots of other things, so undoubtedly we'll see plenty of gains in in quantum applications.
- lurquer 9y ago
  In the early 90's Ghandi got hold of one of these devices and caused havoc. Luckily, he was stopped by Bob Woodward with some help from Elwood Blues and, of course, President Roslin. I'd like to see Qbert crack that.

kilotaras 9y ago

You don't need quantum computers for primality tests. https://en.wikipedia.org/wiki/Primality_test https://en.wikipedia.org/wiki/Primality_test