MTProto protocol requires some bigint calculations for auth key generation: https://core.telegram.org/mtproto/auth_key.

resPQ#05162463 nonce:int128 server_nonce:int128 pq:string server_public_key_fingerprints:Vector long = ResPQ Here, string pq is a representation of a natural number (in binary big endian format). This number is the product of two different odd prime numbers. Normally, pq is less than or equal to 2^63-1. The value of server_nonce is selected randomly by the server; following this step, it is known to all.

As Webogram is Javascript-based app, we need to solve prime-factorization problem here. There are some existing Javascript libraries for bigint computations. Let's take a look at them.

Probably, the most popular javascript bigint implementation. Is very easy in usage, as it has the same interface as Java BigInteger.

Supports just 64-bit calculations, but that's almost always enough for our needs (see "Task description").

This library was included, because I've found the article http://www.joseprio.com/blog/2013/04/27/biginteger-libraries-for-js/, which says that the library allows to reuse existing arrays when operating with numbers, instead of creating new ones. This feature was considered as important for our task, as there is a big loop with a lot of computations in each iteration. Less used memory => better performance.

The library was pretty tricky to use, because of its functions naming. Also, almost every function has its copy (with _ (underscore) in the end), which does the same as original one, but doesn't create a new bigint var instance. That's what I needed for speed improvement.

The code is available in this repo, you can start browsing here: https://github.com/zhukov/prime-factorization-benchmark/blob/master/index.html#L30.

The tests are available via GH-pages: http://zhukov.github.io/prime-factorization-benchmark/.

Each test was repeated from 5 to 10 times and the average time was calculated.

You can try to run tests on your platform, just press the corresponding button. For better results, refresh page after each launch.

Here is the table with results for my hardware. The number in corresponding cell is amount in seconds required to compute the primes. Less is better.

As it was expected, Leemon Baird library showed best scores on almost all platforms.

In my case leemon bigint library had problems with GCD function. The result was incorrect, comparing to jsbn. I didn't get inside the library code, I've just replaced:

g = GCD(z, what);

with:

eGCD_(z, what, g, a, b);

Everything worked fine after that.

In order to make every benchmark run equal we should replace Math.random() with predefined values:

var randoms = [
	  0.6780740048270673,
	  0.5422933690715581,
	  0.30996662518009543,
	  0.9001301566604525,
	  0.9054833319969475,
	  .....
  ],
  randomI = 0;

function nextRandomInt (maxValue) {
  if (randomI >= randoms.length) {
    randomI = 0;
  }
  return Math.floor(randoms[randomI++] * maxValue);
};