Timeline for How hard is it to compute the number of prime factors of a given integer?
Current License: CC BY-SA 2.5
15 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 13, 2017 at 12:58 | history | edited | CommunityBot |
replaced http://mathoverflow.net/ with https://mathoverflow.net/
|
|
| Sep 13, 2010 at 5:04 | history | edited | Charles |
edited tags
|
|
| Dec 30, 2009 at 21:18 | vote | accept | Rune | ||
| Dec 29, 2009 at 20:30 | answer | added | Terry Tao | timeline score: 89 | |
| Dec 29, 2009 at 15:15 | answer | added | Steve Flammia | timeline score: 8 | |
| Nov 6, 2009 at 5:23 | answer | added | paarshad | timeline score: 4 | |
| Nov 3, 2009 at 2:16 | comment | added | Harrison Brown | After thinking about it some more, I suspect that some variant on Pollard's rho might be able to do better for the promise problem than, say, GNFS factorization would, though still nowhere near polynomial. Still, I wonder how far you can push that idea. | |
| Nov 2, 2009 at 23:53 | comment | added | Rune | That's a good point. It would be interesting to see if it were possible to solve the promise problem you stated. | |
| Nov 2, 2009 at 22:28 | comment | added | Harrison Brown | I'd actually like to even see an algorithm that does the following: given a (large) integer n and promised that n has either 2 prime factors or between (ln ln n)^2 and 2(ln ln 2)^2 prime factors, it decides which in polynomial time (or even just faster than by factoring the numbers). This seems like it could be doable, since on average n would be expected to have just ln ln n prime factors, but I don't have a clue where you'd start. | |
| Nov 2, 2009 at 19:41 | comment | added | Ilya Nikokoshev |
Finding out whether a number has 2 versus >2 prime factors already seems inaccessible to me.
|
|
| Nov 2, 2009 at 19:35 | answer | added | Harrison Brown | timeline score: 20 | |
| Nov 2, 2009 at 19:10 | comment | added | Harrison Brown | Determining whether the number of distinct prime factors is exactly 1 is also in P, via the easy trick of computing approximate kth roots for k < log n. | |
| Nov 2, 2009 at 17:32 | comment | added | Rune | Both questions are interesting to me. | |
| Nov 2, 2009 at 17:28 | comment | added | Qiaochu Yuan | Distinct or with multiplicity? | |
| Nov 2, 2009 at 17:25 | history | asked | Rune | CC BY-SA 2.5 |