Re: Factoring small numbers

[Karim Belabas <Karim.Belabas@math.u-bordeaux.fr>]

* Jeroen Demeyer [2014-05-08 18:40]:
> While working on Sage today, I was very amazed that GAP is much faster than
> PARI for factoring small numbers.
> 
> For example, for factoring 19180172397815991981, GAP beats PARI by a factor
> of about 20. As far as I know, PARI uses rho + MPQS while GAP only uses
> Pollard rho. So perhaps PARI shouldn't use MPQS for numbers of this size.
> 
> Any opinions?

Benchmarking the factorization of a single small integer is not very
useful. Can you try a set of about 1000 "random" integers of the same
size ? (and share your benchmark code :-)

You can play with

  factor(a, n)   \\ that's for trial division
  factorint(a, combinations of flags 1/2/4/8)

to see if disabling particular factorization engines helps.

N.B. For your original example, it doesn't help: I got nowhere near
a factor 20, at most 30% improvement (by trying settings that were
quite harmful on average for 65-bit integers, up to 3 x slowdown :-).

N.B.2 Your example is about 4 times slower than the average time 
to factor a (uniform) 65-bit integer. (For which lots of factors are
found via trial division, of course.)

Cheers,

    K.B.
--
Karim Belabas, IMB (UMR 5251)  Tel: (+33) (0)5 40 00 26 17
Universite Bordeaux 1          Fax: (+33) (0)5 40 00 69 50
351, cours de la Liberation    http://www.math.u-bordeaux1.fr/~kbelabas/
F-33405 Talence (France)       http://pari.math.u-bordeaux1.fr/  [PARI/GP]
`