
View Poll Results: Was this helpful and appropriate in this thread?  
yes  2  4.35%  
no  1  2.17%  
maybe  43  93.48%  
Voters: 46. You may not vote on this poll 

Thread Tools 
20200414, 22:25  #1 
Apr 2020
1_{2} Posts 
Factorization using WebAssembly  The fastest in a browser?
What is the fastest way to factorize numbers purely in a browser?
Normally, stateoftheart factorization programs have to be downloaded and run on the command line (like cadonfs or msieve) or in a GUI (like in CrypTool 2, which contains also an Msieve implementation). The CrypTool project (www.cryptool.org) recently evaluated how fast the WebAssembly technology already is and so ported the C library from Msieve to WebAssembly. The source code and a short build description is here: https://github.com/ctonline/MsieveWeb The result is a plugin which works completely within your local browser. This result can be tested in the opensource project CrypToolOnline at https://www.cryptool.org/en/ctohighlights/msieve What we would like to know is:  What other integer factorization implementations are there which can be started in a browser?  Which of them runs purely locally in the browser?  Is there an implementation running only locally in a bowser, which is faster than the one in CrypToolOnline mentioned above?  What can be improved in this implementation? For our tests we used e.g. the following composite number: IntegerPart((2^2041)/2) = = 12855504354071922204335696738729300820177623950262342682411007. Examples of other web prime factorization tools we found are:  https://www.numberempire.com/numberfactorizer.php Limited to 60 decimal digits  https://cocalc.com SageMath running on the CoCalc server (its accessible via the browser, but doesn't run locally purely within the browser)  www.wolframalpha.com Input: factor IntegerPart((2^2041)/2) (its accessible via the browser, but doesn't run locally purely within the browser)  FactorDB.com Input: factor (2^2042)/2 (its accessible via the browser, but doesn't run locally purely within the browser; client workers pick up new composites; result is persistently cached 'forever') Thanks for your feedback. 
20200414, 23:56  #2 
"Robert Gerbicz"
Oct 2005
Hungary
11·127 Posts 
Clearly you haven't tested it, some random inputs:
for x=0: there is no output. for x=1: you write: Factorization: (is a prime) Revisit your math books. for x=1000000!/999999! you write: 1000000!/999999! expression is not an natural number. What is totally false, and here you have a spelling mistake. 
20200415, 00:11  #3 
"Robert Gerbicz"
Oct 2005
Hungary
11·127 Posts 
One more tricky input:
x=4^(1/2)*4^(1/3)*4^(1/6) and you write: Number 2^(4/3)*4^(1/3) (4^(1/2)*4^(1/3)*4^(1/6)) 2^(4/3)*4^(1/3) expression is not an natural number What is also false, it is a natural number. My suggestion: don't offer these, if you can't implement. Ask for a simple integer without using any operator. Last fiddled with by R. Gerbicz on 20200415 at 00:12 
20200415, 02:12  #4 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2
10001110100110_{2} Posts 

20200415, 07:08  #5 
Romulan Interpreter
Jun 2011
Thailand
3^{2}×971 Posts 
You scared him, and now he rounds everything to integers
I tried (2^2473)/12 and it didn't have any issue to factor it... (in spite of the fact that it can't be an integer, as I divide an odd to an even). Joking apart, my only observation to it (after 510 minutes test) is that is only single threaded, and it only uses the amount of CPU computing power that is allowed for the browser (which can be seen immediately with task manager). Syntax and grammar and formula parser can be fixed, but the speed will never beat yafu/msieve local runs, in all cores, not browser restricted, unless you give your browser "unhealthy" freedom. Or, as Serge mentioned, use factordb which doesn't use your resources (well, to paraphrase Retina, that's cheating! ) Last fiddled with by LaurV on 20200415 at 07:10 
20200415, 08:06  #6 
Sep 2006
Brussels, Belgium
11000100100_{2} Posts 
Wouldn't "Alpertron"'s webpage https://www.alpertron.com.ar/ECM.HTMcorrespond to what the OP wants to achieve ?
Jacob 
20200415, 16:52  #7 
Tribal Bullet
Oct 2004
3,529 Posts 
Alpertron has worked in this area for many years, and I assume his work would be difficult to outrun. That being said a 300 bit number in around 20 minutes on my laptop is surprisingly good
I hope they aren't relying on Msieve's formula parser, which is really primitive. 
20200415, 17:25  #8  
"Ben"
Feb 2007
CDA_{16} Posts 
Quote:
Do you know of any good references for algorithms that can deal with such things for exact integer expression solving? 

20200415, 18:59  #9  
Bamboozled!
"πΊππ·π·π"
May 2003
Down not across
10,243 Posts 
Quote:
I will try to dig up a reference (probably Knuth because he's thought deeply about such issues) which states that some "real" arithmetic^{*} algorithms yield more accurate results in less computation with rational arithmetic than with standard floating point arithmetic. The basic idea is to convert all FP quantities into rationals of the form a / 2^{n} and proceed from there, waiting until the final result is available before converting back into floating point format. Careful treatment of quantization and rounding errors is required, but that is also true of FP arithmetic. * I believe he notes that floating point formats are actually elaborated encoded integers. 

20200425, 01:51  #10  
Aug 2002
Buenos Aires, Argentina
3^{3}×7^{2} Posts 
Quote:
But for an intermediate value, such as 10^59+213, it takes 4.3 seconds in my desktop, but his port of msieve to WebAssembly requires about 6 seconds. There is also a glitch in his implementation that after the factorization finishes, the progress bar continues moving, as if the factorization had not finished. It is possible to perform multithreading in WebAssembly but it only works on Chrome at this moment, so I have not implemented it yet. Last fiddled with by alpertron on 20200425 at 01:55 

20200425, 10:03  #11 
Romulan Interpreter
Jun 2011
Thailand
3^{2}×971 Posts 
This is in Firefox since version 54 (in 2017 or so) you need to play with the "about:..." stuff (google, google), but you would be crazy to let a browser use all your computing power, unless you always access THE SAME, secured, pages that you know, every day, etc, and even so, it is not safe... Lots of "miners" there lurking in the dark, waiting to take some satoshies from you during you visit their page...

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Factoring using FFT on the Web browser  alpertron  Programming  6  20180916 12:56 
Primo Browser?  PawnProver44  Information & Answers  14  20160409 05:49 
The Fastest Path  a1call  Puzzles  23  20160323 17:46 
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 