HP 50g Programming Competition: How Many Partitions of an Integer in 4 Squares

[Thomas Ritschel]

(04-19-2018 04:52 PM)Valentin Albillo Wrote:  I did download it to my Samsung tablet (a present, I don't do "smartphones") and verified your timing and factorization (mine are even faster), and also tried to factorize

(720^20-19)*(720^20+19)

which obviously has the factors 720^20-19 and 720^20+19 (both prime) but it didn't succeed and after a long while I had to cancel it.

It did surprise me because this one is an easy case for the much simpler and less powerful Fermat's factorization method (cf. Wikipedia) and as I'm aware that most advanced factorization procedures first of all get rid of all small factors by merely performing a preliminary step of trial division up to some prime limit (say up to 131071), thus I thought that they would next run a short trial of Fermat's method to get rid of comparable large factors and only then would they use their advanced procedures (quadratic sieve, elliptic curves, etc).

Regrettably it seems this implementation for Android doesn't do that or it would have factorized this product instantly.

V.
.

Well, it's not an issue of the Android implementation alone. Even Pari/GP on a PC isn't able to factorize the product (720^20-19)*(720^20+19) in reasonable time (canceled after about 15 minutes). The "factorint" routine does only trial factoring, no advanced methods.