Timeline for Fastest way to factor integers < 2^60
Current License: CC BY-SA 3.0
38 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jan 27, 2020 at 22:52 | comment | added | Lehs | Pollard rho can be coded to not exceed the 64 bit limit. | |
| Nov 26, 2012 at 22:06 | history | edited | Kevin Acres | CC BY-SA 3.0 |
Update on status
|
| Nov 22, 2012 at 16:09 | comment | added | Ng Yong Hao | I missed the comment that the numbers are of a special form and hence limited in possibility. I added another possible way of handling this using a lookup table. | |
| Nov 22, 2012 at 14:16 | answer | added | Someone | timeline score: 5 | |
| Nov 22, 2012 at 10:37 | answer | added | none | timeline score: 3 | |
| Nov 22, 2012 at 9:01 | comment | added | Kevin Acres | @François: I've tried gp2c and gp2c-run a few times, without too much success. Currently I get a segmentation fault. I've had a very busy semester and haven't been able to even start to address these issues until now. | |
| Nov 22, 2012 at 8:20 | comment | added | François Brunault | Not sure whether this would solve the memory problems, but did you already try to use gp2c? pari.math.u-bordeaux.fr/pub/pari/manuals/gp2c/gp2c.html | |
| Nov 22, 2012 at 4:34 | answer | added | Ng Yong Hao | timeline score: 7 | |
| Nov 22, 2012 at 4:09 | answer | added | Igor Rivin | timeline score: 1 | |
| Nov 22, 2012 at 2:32 | answer | added | none | timeline score: 3 | |
| Nov 21, 2012 at 22:36 | comment | added | Kevin Acres | @Gerhard: The difference d must be associated with the same x, multiple times. Currently I'm looking at 4 or more occurrences. | |
| Nov 21, 2012 at 22:28 | comment | added | Gerhard Paseman | OK. Is it important that difference d be associated at least 4 times with the same x, or is it ok that it appear (say) 3 times as associated x^3 - y^3 for 3 different y's and once associated with (x+2)^3 - z^3, assuming all appropriate quantities are within range? Gerhard "Likes To Find Computational Shortcuts" Paseman, 2012.11.21 | |
| Nov 21, 2012 at 22:14 | comment | added | Kevin Acres | @Gerhard: The process is that I iterate through numbers of the form x^3-x'^3, where 0 < x' < x and x > 500,000. From the results I then derive the difference of divisor pairs and store the even values in an array. Once x' has reached 1 then I sort the array and extract values which appear 4 or more times. These then go on for further processing outside the scope of this question. Then x is incremented and I start the whole thing over again. So I'm hoping that there may be a way to short-circuit the process, but in the meantime I'll settle for fast 64 bit factoring. | |
| Nov 21, 2012 at 22:04 | comment | added | Gerhard Paseman | So if I were to give you a set S of differences of the desired form and a way for each difference d to produce four or more numbers N such that each N was a difference of small cubes and had d as a divisor difference, and (big if) if S turned out to be an arithmetic progression or union of a small number of such progressions, would that help? And would you need to store all of S or just the lengths, offsets and differences? Gerhard "Ask Me About System Design" Paseman, 2012.11.21 | |
| Nov 21, 2012 at 21:04 | comment | added | jjcale | Maybe you should ask this question in the forum mersenneforum.org . | |
| Nov 21, 2012 at 20:56 | comment | added | Kevin Acres | @William: I'll take a look at flint. It looks as though it may give me the speed that I need. Thanks for the heads up on that. I'm writing the new code in C, so it looks as though it may be simple to implement. | |
| Nov 21, 2012 at 20:54 | comment | added | Kevin Acres | @Gerhard: I need to determine and store all the even differences in divisors. From here I then look for multiple occurrences of any given value. Currently I look for 4 or more before accepting that value as a candidate. | |
| Nov 21, 2012 at 20:30 | answer | added | Will Jagy | timeline score: 4 | |
| Nov 21, 2012 at 20:07 | comment | added | Gerhard Paseman | In storing the divisor difference pairs, do you just need the numbers, or do you need to know that N=x^3-y^3~L, where the L is the list of divisor differences associated with N? If you just need the heap of differences for all N, there is probably elementary theory that tells you which intervals are populated solely by such differences. Gerhard "Representation As Important As Meaning" Paseman, 2012.11.21 | |
| Nov 21, 2012 at 19:55 | history | edited | Kevin Acres | CC BY-SA 3.0 |
Added more detail on the project.
|
| Nov 21, 2012 at 19:17 | answer | added | user13113 | timeline score: 2 | |
| Nov 21, 2012 at 12:46 | comment | added | William Hart | I assume you are not able to interface directly with C code. If you were, you could use the n_factor function in flint (flintlib.org). First use the algebraic factorisation suggested above, then factor the remaining parts with flint. According to timings I have, you should easily hit 20,000,000 factorisations an hour on recent hardware. | |
| Nov 21, 2012 at 11:58 | answer | added | user9072 | timeline score: 11 | |
| Nov 21, 2012 at 8:34 | answer | added | Laurent Berger | timeline score: 8 | |
| Nov 21, 2012 at 8:12 | comment | added | Gerhard Paseman | Regarding your divisor difference problem, you might be able to do the following: If you have abc - d as one difference, you can add (ab-1)(d-c) to it to get abd-c. That might be useful in generating some of your differences quickly. Gerhard "Ask Me About System Design" Paseman, 2012.11.21 | |
| Nov 21, 2012 at 7:57 | comment | added | Gerhard Paseman | Also, a lot of the interesting prime factors will have the form 6n+1, which can halve the processing time. And if you are not wedded to order, you can arrange the work based on whether (x-y) is 0,1, or 2 mod 3 for some efficiencies. Gerhard "Ask Me About Mature Optimization" Paseman, 2012.11.20 | |
| Nov 21, 2012 at 7:42 | comment | added | Gerhard Paseman | Well, you can start with algebraic factorization of (using x and y) (xx +xy +yy) (x-y), which should reduced the number of needed bits substantially. Will Jagy might have further ideas for processing the big factor. Gerhard "Any Other Nice Algebraic Properties?" Paseman, 2012.11.20 | |
| Nov 21, 2012 at 7:32 | history | edited | Kevin Acres | CC BY-SA 3.0 |
Additional information added to question.
|
| Nov 21, 2012 at 7:23 | comment | added | Kevin Acres | @Gerhard: I'll need to be able to perform about 4 million such factorisations in a day. The numbers are all of the form $x^3-x'^3$, with $x > 500,000$ and $0 < x' < x$, so currently $2^{57}$ is the worst case. | |
| Nov 21, 2012 at 6:42 | answer | added | Will Jagy | timeline score: 4 | |
| Nov 21, 2012 at 6:30 | comment | added | Gerhard Paseman | Lets say about 1.07 billion instead of $2^30$. Gerhard "Apologies Sent Over The Atlantic" Paseman, 2012.11.20 | |
| Nov 21, 2012 at 6:27 | comment | added | Gerhard Paseman | There are roughly 51 million primes less than $2^30$, so a trial factorization of one number on a laptop should be doable in anywhere from under a minute to under a day. Many numbers (perhaps 65% or more of those with 60 binary digits) have all factors under 2^40, so a lot of the numbers can be completely factored with trial division in under an hour. Knowing this, even to within an order of magnitude, does no good unless we know how many numbers he wants to factor and if they are of some advantageous form or not. Gerhard "Ask Me About Rough Mathematics" Paseman, 2012.11.20 | |
| Nov 21, 2012 at 6:25 | comment | added | Will Jagy | @Andrej, I am fairly confident you mean ballpark estimate. | |
| Nov 21, 2012 at 4:45 | comment | added | Andrej Bauer | Can someone make a bulkpart estimate on how much time this would take on a typical computer using naive methods? | |
| Nov 21, 2012 at 4:35 | answer | added | Watson Ladd | timeline score: 7 | |
| Nov 21, 2012 at 4:26 | history | edited | Kevin Acres | CC BY-SA 3.0 |
Swapped out cores for cpus.
|
| Nov 21, 2012 at 4:23 | comment | added | Gerhard Paseman | I don't think you will get a satisfying answer. If you know something about how the integers are distributed, you may find some economies of scale by sieving large intervals or sieving arithmetic progressions. If you are just being thrown integers willy-nilly, trial factorization by doing gcd against primorial fragments may be your best bet for speed improvements. You might gain some ground by trying to factorize products of the integers, but without knowing how they are distributed, it might slow things down. Gerhard "Ask Me About System Design" Paseman, 2012.11.20 | |
| Nov 21, 2012 at 4:07 | history | asked | Kevin Acres | CC BY-SA 3.0 |