5 ms·
> "Qubits will endow quantum computers with the ability to do certain tasks—such as querying a database, factoring large prime numbers..." Why do people make t
by williamstein 9y ago
> "Qubits will endow quantum computers with the ability to do certain tasks—such as querying a database, factoring large prime numbers..."
Why do people make that mistake so often?
- AndrewGaspar 9y agoI'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 agoThe 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 agoThe lay audience might ignore semi-prime and just interpret it as prime. Or the author did that.
- deleted 9y ago[deleted]
- AndrewGaspar 9y agoOh, I see! Thank you for the explanation!
- aiCeivi9 9y agoPeople 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 agoIndeed; 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 agoIn 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 agoYou don't need quantum computers for primality tests. https://en.wikipedia.org/wiki/Primality_test https://en.wikipedia.org/wiki/Primality_test
- vinceguidry 9y agoMy guess is because takes more words to say what they really mean, numbers with only two large prime factors.
- pzh 9y agoMost likely the author misunderstood and incorrectly translated the technical term "prime factorization", which means factoring into primes, to "factoring primes".
- spicymaki 9y agoI think what the person might have meant was factoring a large composite number made up of two large prime numbers. It really is factoring large semiprimes. To make it even more confusing finding the prime factors out of any positive integer is called prime factorization. I totally get why people would say factoring large primes even though that is totally incorrect.