# Is prime factorization by simple algorithm impossible? **URL:** \ **Category:** Factual Questions\ **Created:** [January 21, 2019, 5:52pm UTC](https://boards.straightdope.com/t/is-prime-factorization-by-simple-algorithm-impossible/828159 "2019-01-21T17:52:47Z")\ **Posts on this page:** 20\ **Page:** 1
**Author:** ![WernhamHogg](https://avatars.discourse-cdn.com/v4/letter/w/a587f6/32.png) [@WernhamHogg](https://boards.straightdope.com/u/WernhamHogg)\ **Post date:** [January 21, 2019, 5:52pm UTC](https://boards.straightdope.com/t/is-prime-factorization-by-simple-algorithm-impossible/828159/1 "2019-01-21T17:52:47Z")
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. ---
**Author:** ![Babale](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/babale/32/15666_2.png) [@Babale](https://boards.straightdope.com/u/Babale)\ **Post date:** [January 21, 2019, 5:55pm UTC](https://boards.straightdope.com/t/is-prime-factorization-by-simple-algorithm-impossible/828159/2 "2019-01-21T17:55:24Z")
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. ---
**Author:** ![WernhamHogg](https://avatars.discourse-cdn.com/v4/letter/w/a587f6/32.png) [@WernhamHogg](https://boards.straightdope.com/u/WernhamHogg)\ **Post date:** [January 21, 2019, 6:07pm UTC](https://boards.straightdope.com/t/is-prime-factorization-by-simple-algorithm-impossible/828159/3 "2019-01-21T18:07:48Z")
Would they do it by brute force or by algorithm? ---
**Author:** ![Andy\_L](https://avatars.discourse-cdn.com/v4/letter/a/c67d28/32.png) [@Andy\_L](https://boards.straightdope.com/u/Andy_L)\ **Post date:** [January 21, 2019, 6:08pm UTC](https://boards.straightdope.com/t/is-prime-factorization-by-simple-algorithm-impossible/828159/4 "2019-01-21T18:08:45Z")
> [@WernhamHogg](#): > > Would they do it by brute force or by algorithm? By Shor’s algorithm [Shor's algorithm - Wikipedia](https://en.wikipedia.org/wiki/Shor%27s_algorithm) ---
**Author:** ![Thudlow\_Boink](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/thudlow_boink/32/320_2.png) [@Thudlow\_Boink](https://boards.straightdope.com/u/Thudlow_Boink)\ **Post date:** [January 21, 2019, 6:42pm UTC](https://boards.straightdope.com/t/is-prime-factorization-by-simple-algorithm-impossible/828159/5 "2019-01-21T18:42:56Z")
> [@WernhamHogg](#): > > 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. No, no proof. From [Wikipedia](https://en.wikipedia.org/wiki/Integer_factorization): > [@Wikipedia](#): > > No algorithm has been published that can factor all integers in polynomial time… Neither the existence nor non-existence of such algorithms has been proved, but it is generally suspected that they do not exist and hence that the problem is not in class P. 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.” ---
**Author:** ![DPRK](https://avatars.discourse-cdn.com/v4/letter/d/4491bb/32.png) [@DPRK](https://boards.straightdope.com/u/DPRK)\ **Post date:** [January 21, 2019, 6:46pm UTC](https://boards.straightdope.com/t/is-prime-factorization-by-simple-algorithm-impossible/828159/6 "2019-01-21T18:46:49Z")
> [@Thudlow\_Boink](#): > > No, no proof. From [Wikipedia](https://en.wikipedia.org/wiki/Integer_factorization):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.” Yes, this. Any kid in elementary school knows a simple algorithm to factor numbers, but it is a different story to do it quickly for big numbers. ---
**Author:** ![WernhamHogg](https://avatars.discourse-cdn.com/v4/letter/w/a587f6/32.png) [@WernhamHogg](https://boards.straightdope.com/u/WernhamHogg)\ **Post date:** [January 21, 2019, 7:36pm UTC](https://boards.straightdope.com/t/is-prime-factorization-by-simple-algorithm-impossible/828159/7 "2019-01-21T19:36:03Z")
Thanks, all! This is exactly what I needed, and now i have a deeper understanding of it. ---
**Author:** ![Chronos](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/chronos/32/134_2.png) [@Chronos](https://boards.straightdope.com/u/Chronos)\ **Post date:** [January 21, 2019, 8:03pm UTC](https://boards.straightdope.com/t/is-prime-factorization-by-simple-algorithm-impossible/828159/8 "2019-01-21T20:03:49Z")
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. ---
**Author:** ![WernhamHogg](https://avatars.discourse-cdn.com/v4/letter/w/a587f6/32.png) [@WernhamHogg](https://boards.straightdope.com/u/WernhamHogg)\ **Post date:** [January 21, 2019, 8:10pm UTC](https://boards.straightdope.com/t/is-prime-factorization-by-simple-algorithm-impossible/828159/9 "2019-01-21T20:10:30Z")
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? ---
**Author:** ![rat\_avatar](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/rat_avatar/32/255_2.png) [@rat\_avatar](https://boards.straightdope.com/u/rat_avatar)\ **Post date:** [January 21, 2019, 8:17pm UTC](https://boards.straightdope.com/t/is-prime-factorization-by-simple-algorithm-impossible/828159/10 "2019-01-21T20:17:38Z")
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](https://en.wikipedia.org/wiki/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. ---
**Author:** ![Chronos](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/chronos/32/134_2.png) [@Chronos](https://boards.straightdope.com/u/Chronos)\ **Post date:** [January 21, 2019, 8:20pm UTC](https://boards.straightdope.com/t/is-prime-factorization-by-simple-algorithm-impossible/828159/11 "2019-01-21T20:20:39Z")
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. ---
**Author:** ![WernhamHogg](https://avatars.discourse-cdn.com/v4/letter/w/a587f6/32.png) [@WernhamHogg](https://boards.straightdope.com/u/WernhamHogg)\ **Post date:** [January 21, 2019, 8:25pm UTC](https://boards.straightdope.com/t/is-prime-factorization-by-simple-algorithm-impossible/828159/12 "2019-01-21T20:25:33Z")
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. ---
**Author:** ![leahcim](https://avatars.discourse-cdn.com/v4/letter/l/b4bc9f/32.png) [@leahcim](https://boards.straightdope.com/u/leahcim)\ **Post date:** [January 21, 2019, 8:36pm UTC](https://boards.straightdope.com/t/is-prime-factorization-by-simple-algorithm-impossible/828159/13 "2019-01-21T20:36:50Z")
The most recent number I’ve heard of being factored by a quantum device is [56153](https://phys.org/news/2014-11-largest-factored-quantum-device.html), although using a different method than Shor’s algorithm. Recent paper on quantum annealing for prime factorization: [[1804.02733] Quantum Annealing for Prime Factorization](https://arxiv.org/abs/1804.02733) ---
**Author:** ![Lemur866](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/lemur866/32/434_2.png) [@Lemur866](https://boards.straightdope.com/u/Lemur866)\ **Post date:** [January 21, 2019, 8:41pm UTC](https://boards.straightdope.com/t/is-prime-factorization-by-simple-algorithm-impossible/828159/14 "2019-01-21T20:41:44Z")
> [@WernhamHogg](#): > > 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? 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. ---
**Author:** ![WernhamHogg](https://avatars.discourse-cdn.com/v4/letter/w/a587f6/32.png) [@WernhamHogg](https://boards.straightdope.com/u/WernhamHogg)\ **Post date:** [January 21, 2019, 8:42pm UTC](https://boards.straightdope.com/t/is-prime-factorization-by-simple-algorithm-impossible/828159/15 "2019-01-21T20:42:00Z")
[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] I’ll take their word for it. ---
**Author:** ![WernhamHogg](https://avatars.discourse-cdn.com/v4/letter/w/a587f6/32.png) [@WernhamHogg](https://boards.straightdope.com/u/WernhamHogg)\ **Post date:** [January 21, 2019, 8:43pm UTC](https://boards.straightdope.com/t/is-prime-factorization-by-simple-algorithm-impossible/828159/16 "2019-01-21T20:43:09Z")
> [@Lemur866](#): > > 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. Then I remember it correctly. ---
**Author:** ![ftg](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/ftg/32/2801_2.png) [@ftg](https://boards.straightdope.com/u/ftg)\ **Post date:** [January 21, 2019, 9:40pm UTC](https://boards.straightdope.com/t/is-prime-factorization-by-simple-algorithm-impossible/828159/17 "2019-01-21T21:40:00Z")
> [@rat\_avatar](#): > > 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](https://en.wikipedia.org/wiki/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. 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. ---
**Author:** ![snoe](https://avatars.discourse-cdn.com/v4/letter/s/43a26b/32.png) [@snoe](https://boards.straightdope.com/u/snoe)\ **Post date:** [January 21, 2019, 9:40pm UTC](https://boards.straightdope.com/t/is-prime-factorization-by-simple-algorithm-impossible/828159/18 "2019-01-21T21:40:17Z")
> [@Chronos](#): > > 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. (Emphasis mine) I am so angry I never learned [this](https://en.wikipedia.org/wiki/Euclidean_algorithm) until right now. :smack: > [@](#): > > For illustration, the Euclidean algorithm can be used to find the greatest common divisor of _a_ = 1071 and _b_ = 462. To begin, multiples of 462 are subtracted from 1071 until the remainder is less than 462. Two such multiples can be subtracted (_q_0 = 2), leaving a remainder of 147: > 1071 = 2 × 462 + 147. Then multiples of 147 are subtracted from 462 until the remainder is less than 147. Three multiples can be subtracted (_q_1 = 3), leaving a remainder of 21: > 462 = 3 × 147 + 21. Then multiples of 21 are subtracted from 147 until the remainder is less than 21. Seven multiples can be subtracted (_q_2 = 7), leaving no remainder: > 147 = 7 × 21 + 0. Since the last remainder is zero, the algorithm ends with 21 as the greatest common divisor of 1071 and 462. ---
**Author:** ![DPRK](https://avatars.discourse-cdn.com/v4/letter/d/4491bb/32.png) [@DPRK](https://boards.straightdope.com/u/DPRK)\ **Post date:** [January 21, 2019, 9:52pm UTC](https://boards.straightdope.com/t/is-prime-factorization-by-simple-algorithm-impossible/828159/19 "2019-01-21T21:52:50Z")
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). ---
**Author:** ![leahcim](https://avatars.discourse-cdn.com/v4/letter/l/b4bc9f/32.png) [@leahcim](https://boards.straightdope.com/u/leahcim)\ **Post date:** [January 21, 2019, 10:30pm UTC](https://boards.straightdope.com/t/is-prime-factorization-by-simple-algorithm-impossible/828159/20 "2019-01-21T22:30:28Z")
> [@Lemur866](#): > > …but for very large numbers you might have to keep working on it for millions of years. This is an understatement. Typical back-of-the-envelope calculations for modest-sized semiprimes are measured in universe-lifetimes. [Next page](https://boards.straightdope.com/t/is-prime-factorization-by-simple-algorithm-impossible/828159.md?page=2)