5

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?

hiprivet
  • 160
  • How large is the number? – Ketan Jul 09 '14 at 16:34
  • It is a FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141 in decimal, 78 characters in length. – hiprivet Jul 09 '14 at 16:37
  • 1
    May be it is a system config/capacity issue. Works for me: $ factor 115792089237316195423570985008687907852837564279074904382605163141518161494337 115792089237316195423570985008687907852837564279074904382605163141518161494337: 115792089237316195423570985008687907852837564279074904382605163141518161494337 – Ketan Jul 09 '14 at 16:40
  • Thanks for your answer! Don't know why it's not working on my as working on yours. – hiprivet Jul 09 '14 at 16:45
  • @hiprivet: You are running 32-bit or 64-bit machine? – cuonglm Jul 09 '14 at 16:48
  • @Gnouc: 32-bit, with i686-pae kernel. – hiprivet Jul 09 '14 at 16:57
  • 1
    You can use ruby. Ruby has the ability to handle obscenely long numbers. require 'prime'; puts(0xffffdeadbeef.prime_division.inspect). – phemmer Jul 09 '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 09 '14 at 19:35

2 Answers2

6

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
cuonglm
  • 153,898
  • 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) – phemmer Jul 09 '14 at 17:03
  • @gnouc, that should be: can not handle number larger than 2**32-1 – ctrl-alt-delor Jul 09 '14 at 18:06
  • @Patrick: No, it's not the logic here. factor can work on arbitrary-precision numbers. In info factor, you can see that factor works well with number up to 2**64-1. I see in factor source that it uses uintmax_t, which is always 64 bits. – cuonglm Jul 09 '14 at 18:12
  • @Gnouc That just supports my argument. OP's number is WAY bigger than 2**64-1. – phemmer Jul 09 '14 at 18:59
  • @Patrick: I don't understand what you mean. factor can work with arbitrary-precision, it's mean that with number bigger than 2**64-1. But in 32-bit machine, it causes long integer overflow when number greater than 2**64-1. – cuonglm Jul 09 '14 at 19:03
  • file $(which factor): /usr/bin/factor: ELF 64-bit LSB executable. factor 115792089237316195423570985008687907852837564279074904382605163141518161494337: factor: ‘115792089237316195423570985008687907852837564279074904382605163141518161494337’ is too large. – phemmer Jul 09 '14 at 19:17
  • @Patrick: What is output of ldd /usr/bin/factor? – cuonglm Jul 09 '14 at 19:20
  • @Gnouc linux-vdso.so.1 libc.so.6 /lib64/ld-linux-x86-64.so.2 – phemmer Jul 09 '14 at 19:41
  • 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 09 '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 09 '14 at 19:46
  • @Gnouc But going back to my very first statement, the machine architecture has nothing to do with that big long number. If the code can handle numbers larger than the CPU type, then it doesn't matter if it's 64-bit, 32-bit, or 8-bit. – phemmer Jul 09 '14 at 19:47
  • @Patrick: No, you can check in factor source, it use xstrtoumax to convert string to integer, and will raise LONGINT_OVERFLOW if it can't. I have tested in 32-bit machine and it always raises error. – cuonglm Jul 09 '14 at 19:53
  • @MarkPlotnick: In my openSUSE 64-bit, % factor 170141183460469231731687303715884105727 170141183460469231731687303715884105727: 170141183460469231731687303715884105727 – cuonglm Jul 09 '14 at 19:54
  • 2
    @richard No: factor supports 64-bit numbers on most 32-bit platforms. – Gilles 'SO- stop being evil' Jul 09 '14 at 20:11
  • Compiled with GMP, still gives the "is too large" error. I used pari/GP (apt-get install pari-gp, then run gp) as mentioned in another answer. That factored it in about one second. – Luc Oct 05 '16 at 20:54
6

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.

vinc17
  • 12,174
  • +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 05 '16 at 20:52