The specified number comprising 78 digits has two factors: one is
1238926361552897 comprising 16 digits, and the other has 62 digits.
The factors of 1238926361552897 - 1 are 2^11, 157 and 3853149761; the
size of 3853149761 is crucial to some algorithms: Maxima that uses
the Pollard rho algorithm requires O(2 sqrt(3853149761) ) operations
on big numbers, which is practicable; specifically, Maxima uses the
Pollard rho 1 algorithm and elliptic-curve methods.
Although Maple tries this algorithm, after iterations of fixed
number, it switches to another algorithm that is superior in the sense
that it does not depend on the original number having a small factor.
For the number
1055400183181843712441257014479851392352451420300133289479505613701003
that comprises 70 digits -- hence eight digits less than in the original
number -- and has two factors of comparable length, Maxima takes at least
600 times as long as Maple.
I report here calculations made by Michael Monagan.
John Ogilvie
On Sun, 17 Jun 2012, Aleksas Domarkas wrote:
> Factorization of Fermat number F[8]=2^(2^8)+1
> http://en.wikipedia.org/wiki/Fermat_number
> Maple:
>> restart;
>> st := time():
> ifactor(2^(2^8)+1);
> time() - st;
>
> (1238926361552897) (934616397153579777691635581996068965840512\
> 37541638188580280321)
> 230.897
> Maxima:
> (%i1) if showtime#false then showtime:false else showtime:all$
> Evaluation took 0.0000 seconds (0.0000 elapsed)
> (%i2) factor(2^(2^8)+1);
> Evaluation took 3.7800 seconds (3.7800 elapsed)
> (%o2)
> 1238926361552897*93461639715357977769163558199606896584051237541638188580280321
> (%i3) 230.897/3.78;
> (%o3) 61.08386243386244
>
> Conclusion: for factorizing integers maple is 61 slower than maxima.
>