Karim Belabas on Thu, 08 May 2014 20:50:15 +0200 |
[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]
Re: Factoring small numbers |
* 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] `