I'm trying to use a factor utility but it tells me that number is too large. Is there any utility that can do what factor doing but not tells that number is too large?

  • How large is the number? – mkc Jul 9 '14 at 16:34
  • It is a FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141 in decimal, 78 characters in length. – hiprivet Jul 9 '14 at 16:37
  • 1
    May be it is a system config/capacity issue. Works for me: $ factor 115792089237316195423570985008687907852837564279074904382605163141518161494337 115792089237316195423570985008687907852837564279074904382605163141518161494337: 115792089237316195423570985008687907852837564279074904382605163141518161494337 – mkc Jul 9 '14 at 16:40
  • 1
    You can use ruby. Ruby has the ability to handle obscenely long numbers. require 'prime'; puts(0xffffdeadbeef.prime_division.inspect). – Patrick Jul 9 '14 at 17:02
  • 1
    Do not use prime_division.inspect in ruby. It is extremely slow! factor.pl from Math::Prime::Util is OK, or use Pari/GP's factor function. For instance, try on: 806578020551755900412008880903137528217525975284037923 – vinc17 Jul 9 '14 at 19:35

Maybe your factor is not built with GMP, so it can not handle number bigger than 2**64-1:

$ factor 18446744073709551616
factor: `18446744073709551616' is too large
$ factor 18446744073709551615
18446744073709551615: 3 5 17 257 641 65537 6700417

Running this command to check if factor built with GMP:

$ ldd /usr/bin/factor 
        linux-vdso.so.1 (0x00007fffda1fe000)
        libgmp.so.10 => /usr/lib64/libgmp.so.10 (0x00007faae00f5000)
        libc.so.6 => /lib64/libc.so.6 (0x00007faadfd46000)
        /lib64/ld-linux-x86-64.so.2 (0x00007faae037c000)

The limit may be higher on some machines (the number has to fit in uintmax_t type), but your number is a 256-bit number, and no common machine supports such a big uintmax_t, if any.

Note that the factor utility can be compiled with GMP support. In that case, there is effectively no limit on the size of the number. It appears that your distribution hasn't activated GMP support (which makes sense since it would add a dependency on an extra library to a core system package for a rarely used feature).

If you have perl, you can try factor.pl program include in Math::Prime::Util module:

$ /home/cuonglm/.cpan/build/Math-Prime-Util-0.31-9c_xq3/bin/factor.pl 115792089237316195423570985008687907852837564279074904382605163141518161494337
115792089237316195423570985008687907852837564279074904382605163141518161494337: 115792089237316195423570985008687907852837564279074904382605163141518161494337
| improve this answer | |
  • 4
    By this logic, FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141 shouldn't work even on a 64-bit system as that's WAY bigger than 64 bit. (and indeed it doesn't on my system, which is 64-bit) – Patrick Jul 9 '14 at 17:03
  • @gnouc, that should be: can not handle number larger than 2**32-1 – ctrl-alt-delor Jul 9 '14 at 18:06
  • 2
    @Patrick: Oh, your factor does not buid with GNU MP, so it can not handle arbitrary-precision numbers. See info factor for more details. – cuonglm Jul 9 '14 at 19:43
  • 1
    Newer versions of factor in coreutils use 2 uint64_t's, or GMP if chosen when compiled. The maximum it can handle on my 64-bit ubuntu system is 2^127-1, so apparently it wasn't built with GMP. – Mark Plotnick Jul 9 '14 at 19:46
  • 2
    @richard No: factor supports 64-bit numbers on most 32-bit platforms. – Gilles 'SO- stop being evil' Jul 9 '14 at 20:11

You can also use factor from the coreutils. However it needs to be compiled with bignum support. FYI, this is not the case with the binary that comes with some distributions, such as Debian (bug 608832). But you can download the source and recompile it after installing GMP (which is used by default if found).

Another solution is to use Pari/GP (well-known for number theory):

? factor(806578020551755900412008880903137528217525975284037923)
%1 =
[ 238366085426200783161668947 1]

[3383778439410064898661524209 1]

With this number, it takes a few seconds.

| improve this answer | |
  • +1 for pari/GP, it computed the factors in about a second (single-threaded it seems) while other programs took multiple minutes multi-threaded. I had not heard of the tool before. Tip for others: apt-get install pari-gp then run gp, at least in Debian Stretch. – Luc Oct 5 '16 at 20:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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