View Single Post
Old 2018-09-12, 17:32   #6
alpertron's Avatar
Aug 2002
Buenos Aires, Argentina

23×3×5×11 Posts

Originally Posted by alpertron View Post
Now the calculation of sum of squares uses GCD of Gaussian integers (for two squares) and GCD of quaternions (for four squares).

The GCD takes about 1 second for numbers of 10000 digits (I tested that with the smallest gigantic prime, which is 109999 + 33603). Most of the time is used for a modular power.

With the previous version, computing the sum of four squares would have taken about one hour.

I will continue doing more tests, and if everything works OK, I will move the new Web application to the "standard" URL.
Now when the code detects that the number can be divided by a very small factor (less than 100000), it will quickly determine the maximum exponent of this small factor that can divide the number, so the factorization proceeds a lot faster.

For example, in the previous version the application needed 15 minutes to factor 2678!. In this version it needs only 10 seconds in the same computer.

Now I will need to change the program to quickly compute big factorials (say bigger than 5000!).
alpertron is offline   Reply With Quote