mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Msieve

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

Reply
 
Thread Tools
Old 2020-04-14, 22:25   #1
aware
 
Apr 2020

116 Posts
Question 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 (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.
aware is offline   Reply With Quote
Old 2020-04-14, 23:56   #2
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

17·83 Posts
Default

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 is offline   Reply With Quote
Old 2020-04-15, 00:11   #3
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

17×83 Posts
Default

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 2020-04-15 at 00:12
R. Gerbicz is offline   Reply With Quote
Old 2020-04-15, 02:12   #4
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

23·7·163 Posts
Default

Quote:
Originally Posted by aware View Post
What is the fastest way to factorize numbers purely in a browser?
You simply enter it into Factordb.com, and press Factorize!
Batalov is offline   Reply With Quote
Old 2020-04-15, 07:08   #5
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

887310 Posts
Default

Quote:
Originally Posted by R. Gerbicz View Post
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! )

Last fiddled with by LaurV on 2020-04-15 at 07:10
LaurV is online now   Reply With Quote
Old 2020-04-15, 08:06   #6
S485122
 
S485122's Avatar
 
Sep 2006
Brussels, Belgium

2·7·113 Posts
Default

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

Jacob
S485122 is offline   Reply With Quote
Old 2020-04-15, 16:52   #7
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

3·1,163 Posts
Default

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.
jasonp is offline   Reply With Quote
Old 2020-04-15, 17:25   #8
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

2·17·97 Posts
Default

Quote:
Originally Posted by R. Gerbicz View Post
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?
bsquared is offline   Reply With Quote
Old 2020-04-15, 18:59   #9
xilman
Bamboozled!
 
xilman's Avatar
 
"π’‰Ίπ’ŒŒπ’‡·π’†·π’€­"
May 2003
Down not across

2·61·83 Posts
Default

Quote:
Originally Posted by bsquared View Post
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 / 2n 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.
xilman is offline   Reply With Quote
Old 2020-04-25, 01:51   #10
alpertron
 
alpertron's Avatar
 
Aug 2002
Buenos Aires, Argentina

133310 Posts
Default

Quote:
Originally Posted by jasonp View Post
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.

Last fiddled with by alpertron on 2020-04-25 at 01:55
alpertron is offline   Reply With Quote
Old 2020-04-25, 10:03   #11
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

19·467 Posts
Default

Quote:
Originally Posted by alpertron View Post
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...
LaurV is online now   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Factoring using FFT on the Web browser alpertron Programming 6 2018-09-16 12:56
Primo Browser? PawnProver44 Information & Answers 14 2016-04-09 05:49
The Fastest Path a1call Puzzles 23 2016-03-23 17:46
What browser do you use? Mini-Geek Lounge 12 2007-02-16 06:48
If you haven't yet ditched the Netscape browser... ewmayer Lounge 3 2005-05-10 00:28

All times are UTC. The time now is 17:53.

Wed Oct 28 17:53:39 UTC 2020 up 48 days, 15:04, 2 users, load averages: 1.94, 2.07, 2.14

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.