question on possible factor() function for gmp

Torbjörn Granlund tg at gmplib.org
Fri Jul 6 16:15:48 UTC 2018


logical american <website.reader3 at gmail.com> writes:

  Has someone put together a function for gmp called factor(n) where n
  is integer? (output is a list of factors and their powers)

Probably not.  (I assume you mean prime factors here, else I can provide
a simple function returning 1 and n in a list...)

  I did play around with the Pollard method but when I was working with
  30-40 digit numbers to factor, GP Pari was always faster than gmp in
  this region.

GP Pari's integer factoring code has been quite well optimised, and it
implements several different integer factoring algorithms.  IIRC, they
even have some MPQS variant.

GMP still isn't very fast for numbers of 30-40 decimal digits.  Its
bookkeeping and function call overhead is to large for such small
numbers.

If your interest is factoring just 127-bit numbers (all number up to 38
digits and some 39-digit numbers) then you might want to use the factor
command from GNU coreutils.

-- 
Torbjörn
Please encrypt, key id 0xC8601622


More information about the gmp-discuss mailing list