4
$\begingroup$

What is the best program to factor large arbitrary-form integers on a single computer, or on a few disjointed computers? "Best" is obviously subjective, but what do you recommend?

I'm working on a project to factor general-form numbers that I know are composite, with a scale of 100 - 1000 digits. I have a few computers I can use to process in parallel, but they're nowhere close to a cluster - and they certainly don't have the horsepower / memory needed for something like GNFS.

I've looked around a little, but what I've found can be classified as:

  1. Prove primality of general-form numbers (mine = known composites)
  2. Factor special-form numbers (mine = general-form numbers)
  3. Factor general-form numbers on a huge cluster (no cluster)

I'm missing the last one, "Factor general-form numbers on one or two sneakernet systems".

Final caveats: I'd prefer something free, but I'd be willing to spring for Maple / Mathematica / whatnot if it's my best option. Also I'd prefer something that's already built (binary package), but I can compile from source if that's a better option.

$\endgroup$
7
  • $\begingroup$ So a GPU is out of the question for you? :) $\endgroup$
    – J. M. ain't a mathematician
    Dec 7, 2010 at 16:25
  • $\begingroup$ Not out of the question - if there's a decent algo for GPU it would be cheaper to get 2 or 3 of 'em versus buy Mathematica. Are there GPU algos for 3-4k bit number factorization? $\endgroup$
    – Maelstrom
    Dec 7, 2010 at 16:44
  • $\begingroup$ I'm talking hardware here since factoring an arbitrary large number is inherently computationally intensive. Any algorithm you choose to settle with would greatly benefit from you supplying as much computational power as you can muster. $\endgroup$
    – J. M. ain't a mathematician
    Dec 7, 2010 at 17:03
  • 2
    $\begingroup$ ecm will only give you factors of up to about 70 digits, and only then if you really know what you are doing, and are lucky. For general-form numbers you might be able to factor 150 or 160 digit numbers with msieve (GNFS implementation) on a single machine, if you have enough memory for the matrix solving stage. For numbers much larger than that you're getting to the bleeding edge of research, and the world record is far below 1k bits. $\endgroup$
    – Chris Card
    Dec 7, 2010 at 17:40
  • 1
    $\begingroup$ The "lucky" in Chris's comment cannot be emphasized enough, unfortunately. At the risk of sounding patronizing, one should always do trial division with "small" primes (how many of the first few primes should you divide with is up to you) first before using more advanced methods. $\endgroup$
    – J. M. ain't a mathematician
    Dec 7, 2010 at 18:40

1 Answer 1

Reset to default
7
$\begingroup$

You're asking about a very wide range of numbers!

For all numbers, you should do ECM first. I recommend GMP-ECM (Windows, source).

For numbers of about 100 digits, your best bet (after doing an appropriate amount of trial factorization and ECM) is to use a SIQS. msieve would be a good choice.

For numbers of between 100 and 200 digits, you should do a large amount of ECM, at the very least a CPU-day's worth (and possibly 100+ CPU-days). Once those complete, if no factors were found, you should move to GNFS. GGNFS (Windows, source) is good and does not require a cluster, though for the upper end of the range you'll need at least a year if you're running on a single (multicore, one hopes) machine. Here are some guidelines on using NFS.

You have no hope of factoring hard numbers of 200 to 300 digits without many machines. Thus, for large general-form numbers, you should focus entirely on ECM in hopes of finding a small factor (up to about 60 digits, with patience, or about 70 digits, with patience and good fortune). If you find a factor, the cofactor may well be susceptible to GNFS (or it might be prime).

No one has a reasonable chance to factor hard numbers of 300 to 1000 digits, unless possibly the NSA. You should use ECM on such numbers in hopes of finding a factor, but you're unlikely to finish the factorization even if you do.

Now if you have access to a CUDA-enabled GPU (or several), you can speed the ECM with EECM . I don't know of any tools that do NFS on GPUs.

In short: ECM a lot, then finish off with SIQS or NFS if the number is small enough (below 180-200 digits depending on your resources and patience). If you want to throw money at the problem, buy more hardware, possibly GPUs -- don't buy commercial software, that has no bang for your buck.

$\endgroup$
10
  • $\begingroup$ Well, if he could get one of those Tesla GPU suckers, he might stand an even better chance of doing things in shorter time... $\endgroup$
    – J. M. ain't a mathematician
    Dec 8, 2010 at 0:33
  • $\begingroup$ Admittedly, I haven't touched on factoring large numbers in quite a number of years (real life gets in the way of mathematical endeavors ;) ), and I haven't seen anybody write CUDA stuff implementing sieve methods. Based on the implementation of CUDA I've seen, though, I can't see why it's not possible to write a CUDA implementation of NFS. $\endgroup$
    – J. M. ain't a mathematician
    Dec 8, 2010 at 1:09
  • $\begingroup$ @J. M.: I agree, in principle it can be done. But there's a wide gulf between 'can be done' and 'has been done', and since this sounded like a practical question I stayed away from the 'could be done's. $\endgroup$
    – Charles
    Dec 8, 2010 at 14:01
  • 1
    $\begingroup$ @Maelstrom: SIQS is entirely inappropriate for a number that large. Even NFS would be too slow for you. You need to use ECM. Does Alpertron's applet say what B1 values it's on now? Failing that, what does it say in terms of its current progress? I may be able to advise. $\endgroup$
    – Charles
    Dec 10, 2010 at 18:32
  • 1
    $\begingroup$ And not to be overly self-promotional, but since you're new to the site: you can vote for my answer by clicking the up arrow by it and select it as the answer by clicking the transparent checkmark. $\endgroup$
    – Charles
    Dec 10, 2010 at 18:34

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .