Factorization using WebAssembly -- The fastest in a browser?

[aware]

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 (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/ct-online/Msieve-Web

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
https://www.cryptool.org/en/cto-highlights/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 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:

- 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^204-1)/2)
(its accessible via the browser, but doesn't run locally
purely within the browser)

- FactorDB.com 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.

[R. Gerbicz]

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.

[R. Gerbicz]

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.

[Batalov]

Originally Posted by aware

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

You simply enter it into Factordb.com, and press Factorize!

[LaurV]

Originally Posted by R. Gerbicz

expression is not an natural number

You scared him, and now he rounds everything to integers
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! )

[S485122]

Wouldn't "Alpertron"'s webpage https://www.alpertron.com.ar/ECM.HTMcorrespond to what the OP wants to achieve ?

Jacob

[jasonp]

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.

[bsquared]

Originally Posted by R. Gerbicz

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.

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?

[xilman]

Originally Posted by bsquared

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

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^* 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ⁿ 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.

[alpertron]

Originally Posted by jasonp

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.

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.

[LaurV]

Originally Posted by alpertron

It is possible to perform multithreading in WebAssembly but it only works on Chrome at this moment, so I have not implemented it yet.

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...