Factorization using WebAssembly -- The fastest in a browser?
 

What is the fastest way to factorize numbers purely in a browser?

Normally, state-of-the-art factorization programs have to be downloaded
and run on the command line (like cado-nfs or msieve) or in a GUI (like
in CrypTool 2, which contains also an Msieve implementation).

The CrypTool project ([URL="http://www.cryptool.org"]www.cryptool.org[/URL]) 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:
[URL]https://github.com/ct-online/Msieve-Web[/URL]

The result is a plugin which works completely within your local browser.
This result can be tested in the open-source project CrypTool-Online at
[URL]https://www.cryptool.org/en/cto-highlights/msieve[/URL]

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 CrypTool-Online mentioned above?
- What can be improved in this implementation?

For our tests we used e.g. the following composite number:
IntegerPart((2^204-1)/2) =
= 12855504354071922204335696738729300820177623950262342682411007.

Examples of other web prime factorization tools we found are:

- [URL]https://www.numberempire.com/numberfactorizer.php[/URL]
Limited to 60 decimal digits

- [URL]https://cocalc.com[/URL]
SageMath running on the CoCalc server
(its accessible via the browser, but doesn't run locally
purely within the browser)

- [URL="http://www.wolframalpha.com"]www.wolframalpha.com[/URL] Input: factor IntegerPart((2^204-1)/2)
(its accessible via the browser, but doesn't run locally
purely within the browser)

- [URL="http://factordb.com"]FactorDB.com[/URL] Input: factor (2^204-2)/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.

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.

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.

[QUOTE=aware;542704]What is the fastest way to factorize numbers purely in a browser?
[/QUOTE]
You simply enter it into [URL="http://factordb.com/"]Factordb.com[/URL], and press [C]Factorize![/C]
:jokedrum:

[QUOTE=R. Gerbicz;542711]expression is not an natural number[/QUOTE]
You scared him, and now he rounds everything to integers :rofl:
I tried (2^247-3)/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 5-10 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! :razz:)

Wouldn't "Alpertron"'s webpage [url=https://www.alpertron.com.ar/ECM.HTM]https://www.alpertron.com.ar/ECM.HTM[/url]correspond to what the OP wants to achieve ?

Jacob

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.

[QUOTE=R. Gerbicz;542712]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.[/QUOTE]

yafu also fails for this input as it requires that all intermediate calculations are also integers. This is an assumption I think a lot of basic integer calculators make. Even it could deal with floats then the result would also be a float. To get an exact integer result this input requires some algebraic manipulations (grouping of exponents) and rational arithmetic in the grouped exponent.

Do you know of any good references for algorithms that can deal with such things for exact integer expression solving?

[QUOTE=bsquared;542780]Do you know of any good references for algorithms that can deal with such things for exact integer expression solving?[/QUOTE]No specific reference, but perhaps such an algorithm might be implemented on top of a rational integer package?

I will try to dig up a reference (probably Knuth because he's thought deeply about such issues) which states that some "real" arithmetic[sup]*[/sup] 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 [I]a[/I] / [I]2[SUP]n[/SUP][/I] 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.

[QUOTE=jasonp;542776]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.[/QUOTE]

Probably for larger inputs his port of msieve is faster because I have not implemented the double large prime variation for SIQS.

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.

[QUOTE=alpertron;543688]It is possible to perform multithreading in WebAssembly but it only works on Chrome at this moment, so I have not implemented it yet.[/QUOTE]
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...

WebAssembly threads requires SharedArrayBuffer. This was implemented on major browsers but since Spectre and Meltdown attacks were found in January 2018, the feature was disabled in both Chrome and Firefox and deleted in Safari.

In Chrome 70 SharedArrayBuffer was enabled again, so this Web browser supports WebAssembly threads with no changes, Firefox requires [I]javascript.options.shared_memory[/I] preference to be set to true. Safari does not have SharedArrayBuffer, so it cannot support WebAssembly threads.

Notice that this does not mean that we cannot use more than one core of the processor to perform factorization, but it is a lot more complex and probably requires more memory for communication between the different processes.

PARI
 

Pari/GP is a fast way to factor numbers purely in your browser. It can factor the number you gave instantly. Try it here:

[url]https://pari.math.u-bordeaux.fr/gpexpwasm.html[/url]

Incidentally, I'm the guy that runs CoCalc, which like you said currently only does computations on a Linux machine on Google Cloud Platform. That said, here's a much newer compilation of the Pari using the latest versions of everything, hosted on CoCalc: [url]https://share.cocalc.com/share/79bf90077a47d96142452571b094e9c65bbdcf0c/pari/test/index.html?viewer=share[/url]