Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
So a GPU is out of the question for you? :) –  J. M. Dec 7 '10 at 16:25
    
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? –  Maelstrom Dec 7 '10 at 16:44
    
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. –  J. M. Dec 7 '10 at 17:03
2  
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. –  Chris Card Dec 7 '10 at 17:40
1  
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. –  J. M. Dec 7 '10 at 18:40

1 Answer 1

up vote 6 down vote accepted

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.

share|improve this answer
    
Well, if he could get one of those Tesla GPU suckers, he might stand an even better chance of doing things in shorter time... –  J. M. Dec 8 '10 at 0:33
    
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. –  J. M. Dec 8 '10 at 1:09
    
@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. –  Charles Dec 8 '10 at 14:01
1  
@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. –  Charles Dec 10 '10 at 18:32
1  
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. –  Charles Dec 10 '10 at 18:34

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.