20180820, 18:01  #1 
Aug 2002
Buenos Aires, Argentina
2^{3}×3×5×11 Posts 
Factoring using FFT on the Web browser
I've just updated my factorization tool to use FFT.
Now it can factor numbers up to 100000 digits. Since I made several changes in the program, I've uploaded the alpha version to https://test.alpertron.com.ar/ECM.HTM Please let me know if you find problems. 
20180820, 18:14  #2 
"Robert Gerbicz"
Oct 2005
Hungary
2^{3}×3^{2}×19 Posts 
Tried it on 10^99999, basically it doesn't seem that fast, maybe in a minute it could down to 10^99900 on the unfactored part.

20180820, 18:47  #3 
Aug 2002
Buenos Aires, Argentina
528_{16} Posts 
For numbers of about 10000 digits, it runs about 3 times faster than the previous version that uses Karatsuba.
Of course the applet cannot compete with native programs that can use Assembler. Remember that the code runs inside the Web browser. 
20180820, 19:11  #4  
Sep 2003
2,579 Posts 
Quote:
PS, it's confusing to call it an "applet". It's not an oldtimey Java applet. 

20180909, 18:43  #5 
Aug 2002
Buenos Aires, Argentina
10100101000_{2} Posts 
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 10^{9999} + 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. 
20180912, 17:32  #6  
Aug 2002
Buenos Aires, Argentina
10100101000_{2} Posts 
Quote:
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!). 

20180916, 12:56  #7 
Aug 2002
Buenos Aires, Argentina
2^{3}·3·5·11 Posts 
I found no further errors, so the new factorization application is at its expected location: https://www.alpertron.com.ar/ECM.HTM

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Primo Browser?  PawnProver44  Information & Answers  14  20160409 05:49 
What browser do you use?  MiniGeek  Lounge  12  20070216 06:48 
If you haven't yet ditched the Netscape browser...  ewmayer  Lounge  3  20050510 00:28 