I am not a mathemetician and don’t comprehend abstract math well, so bear with me. I have a pretty simple question but am havinng trouble finding an answer because I’m either led to simple prime factor problems for kids or dense/abstract mathematical theory.
Encryption involves multiplying two very large prime numbers, and reliant on the fact that it takes a very very long time for anyone to work out the prime factors of very large numbers.
What I want to know is if there is mathematical proof that no algorithm will ever exist to derive prime factors easily or if it’s simply assumed that no elite hacker-mathemitician will discover one.
Supposedly this is one of the things a quantum computer could do really, really well. We don’t have quantum computers yet, but we have normal computers that simulate quantum ones (ie they model a quantum computer, taking much longer to get an answer than a real quantum computer would, but arriving at the same result) so the people discussing quantum computing probably know what they are talking about.
Roughly, you can interpret “in polynomial time” or “in class P” to mean “easily” or “quickly enough that it’s practical to do so, without some advance in technology.”
It should be pointed out that there’s a difference between “simple” and “efficient”. The grade school algorithm is indeed simple, and it would (in principle) work even for the numbers used in cryptography. It just works very, very slowly.
EDIT: As an aside, I’m always somewhere between amused and dismayed when I see students being taught to find the greatest common factor of two numbers, by first finding the full factorization of both and then comparing the lists. It’s solving a very easy problem, by first reducing it to a pair of very difficult problems.
I don’t remember the grade school process except trial and error. Like, is it even? Is it divisible by 3? Is it divisible by 5? All of those had quick ways to tell (eg, adding the digits for divisible by 3).
I can’t really get a handle on quantum computing because I know very little about physics. Is this pie in the sky stuff or any day now stuff?
The following problem is still still open as to if it can be reduced to polynomial time.
For a number n, find the smallest prime number p that is greater than n.
Finding p>n is EXPTIME or requires exponential runtime
Currently determining whether a number is prime or can be done in polynomial time but finding the next prime cannot but we also don’t know if finding the next prime is NP-complete.
Nobody can really get a handle on quantum computing. A few physicists have managed to figure out how to do the calculations without needing to have a handle. But as Richard Feynman said, anyone who thinks they understand quantum mechanics doesn’t understand quantum mechanics.
As to the rest, actual quantum computers have in fact been made, and they do in fact work. But so far, theyr’e extremely small scale, such that they can’t be used to do anything that you couldn’t easily do in your head. There’s no fundamental reason that they absolutely can’t be scaled up, but it’s difficult, and there are a lot of stages the technology will have to go through before it’s a serious threat to modern encryption.
People are preparing for this, including by coming up with new encryption algorithms for which it can be proven that a quantum computer can’t do any better than a classical computer (though it’s still not proven that there isn’t some clever, efficient classical algorithm just waiting to be discovered). After all, you don’t want to be caught unprepared when quantum computers do eventually become practical. But none of them are widespread yet, because you also don’t want to be hasty when it comes to security, and implement it before you’re confident that you’ve found and neutralized all of the potential attacks.
This is an interesting topic and I wish I understood it better. I have enough to go on for the shitty science fiction story I am writing though. So thanks.
Except this is an algorithm to find the prime factors of a number. Start with 2, then 3, then 5, then 7, and so on, and find if the modulo is zero. If it is, then the number has that prime factor. If you reach the end of the list then your number is prime and has no prime factors.
This is a simple algorithm to determine the prime factors of any number. It can very quickly find all the prime factors for small numbers. But the amount of work you need to do to find the prime factors gets larger faster than your number gets larger. This algorithm will eventually find all the prime factors of any number, but for very large numbers you might have to keep working on it for millions of years.
[quote=
Shuxian Jiang, Keith A. Britt, Alexander J. McCaskey, Travis S. Humble & Sabre Kais]
We have developed a framework to convert an arbitrary integer factorization problem to an executable Ising model by first writing it as an optimization function and then transforming the k-bit coupling (k≥3) terms to quadratic terms using ancillary variables.
[/quote]
Could you fix this up and cite the main point, please? E.g., I think the last paragraph is supposed to start “Currently determining whether a number is prime or not can be done …” but I can’t parse the rest.
IMHO, finding the next higher prime after n is fairly fast using Miller-Rabin* and the density of primes. But that’s probabilistic.
BTW: Calling this “Miller-Rabin” is just wrong. It should be just “Miller”. Rabin did this sort of, err, “thing” more than once.
One pretty much needs first to know how to find the greatest common divisor of two integers (like in Euclid’s algorithm), in order to apply any fancy algorithm to factor a number, like in the rho-algorithm or various sieve algorithms. In the other direction, like Chronos says, even for small numbers and by hand there is definitely no need to factor numbers to compute their greatest common factor, so one wonders who would push teaching students that (as opposed to the fact that IF you know the complete prime factorization of the numbers then you can easily figure it out).
So thanks.