Timeline for Factoring blocks of numbers
Current License: CC BY-SA 2.5
14 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Nov 15, 2022 at 2:59 | comment | added | D.W. | cstheory.stackexchange.com/q/2049/5038 | |
| Mar 3, 2011 at 22:08 | answer | added | user9680 | timeline score: 0 | |
| Oct 11, 2010 at 20:48 | comment | added | Cam McLeman | Just noting that Eric's original comment says "inappropriate" and not "appropriate," expressing what I read as genuine unsureness (so I don't think Pete actually disagrees). I think the suggestion that it be cross-listed on SO is a fairly reasonable one. | |
| Oct 11, 2010 at 20:30 | answer | added | tdnoe | timeline score: 1 | |
| Oct 11, 2010 at 8:45 | comment | added | Eric Tressler | @Pete: I take your point, but think that it might have attracted interest on stackoverflow also. | |
| Oct 11, 2010 at 5:51 | comment | added | Gerry Myerson | OK, then I think Gerhard has the right idea. Remove all prime factors up to some bound $Q$, test what's left for pseudo-primality with some quick test. Apply a rigorous primality test to the ones that pass the test, and a factorization method like Pollard rho or Pollard $p-1$ to the ones that don't. Details on how some of these tests run can be found in Riesel, Prime Numbers and Computer Methods for Factorization. | |
| Oct 11, 2010 at 4:21 | comment | added | Nameless | Gerry: I am considering N on the order of 10^18 .. 10^20 and n small enough to keep memory requirements within CPU cache of a modern processor (so, under 10^7). | |
| Oct 11, 2010 at 4:01 | comment | added | Pete L. Clark | I agree with Charles and disagree with Eric Tressler: algorithmic number theory is a branch of mathematics, not of computer science. The question seems perfectly on-topic here. | |
| Oct 11, 2010 at 2:36 | comment | added | Eric Tressler | Would you mind explaining how this came up, if it's a practical problem? | |
| Oct 11, 2010 at 2:21 | comment | added | Gerry Myerson | It's not clear to me what ranges you are considering. If $N$ is around $10^{30}$, say, then you are not going to compute and store all the primes up to $\sqrt N$. Then again, if $N$ is around $10^{30}$, and $n$ is near $\sqrt N$, I can hardly see holding, much less factoring, all the numbers from $N$ to $N+n$. So, what do you really want to do? | |
| Oct 11, 2010 at 2:01 | answer | added | Gerhard Paseman | timeline score: 2 | |
| Oct 11, 2010 at 1:31 | comment | added | Charles | I vote for appropriate. | |
| Oct 11, 2010 at 1:09 | comment | added | Eric Tressler | I'm not sure that this is inappropriate here, but you should definitely post this on stackoverflow.com as well. | |
| Oct 11, 2010 at 0:10 | history | asked | Nameless | CC BY-SA 2.5 |