下のテキストボックスに素因数分解したい数字を入力すると、高速で素因数分解を行います。桁数制限はありませんが、速度は端末の処理能力に依存します。

この超高速素因数分解ツールはJavaScriptで処理されており、3つの工夫を行うことによって高速な素因数分解を実現しています。

まず一つ目の工夫は、単純に2から指定された数までmodを計算するのではなく、指定された数の平方根までのmod計算をしている点です。

ところで、JavaScriptの通常の数値型(Number)では16桁(MAX_SAFE_INTEGER)までしか扱えないため、BigIntの平方根を求めるアルゴリズムは独自に実装しなければなりません。

Chromiumの内部実装などを参考とし、以下のように実現しました。

function sqrt_fast(value) {
  let sqrt = value / 3n;
  if (value <= 0n) return 0n;
  for (let i = 0; i < 6; i++)
    sqrt = (sqrt + value / sqrt) / 2n;
  return sqrt;
}

console.log( "16の平方根は" + sqrt( BigInt(16) ) + "です" );

そして二つ目の工夫は、平方根による総当たりmod計算を行う前に、まず素数でないか判定している点です。

Miller–Rabin(ミラーラビン)素数判定法を実装することで、高速で素数の判定を行うことができます。

また、通常のミラーラビン素数判定法を用いるとBigIntの最大値を超えるほどの数が一時的に生成されてしまうため、BigInt用のmodPow関数も独自に実装しました。

function getRandomInt(min, max) {
  return Math.floor(Math.random() * (max - min + 1)) + min;
}
function modPow(a, b, m) {
  if (b === 0n) {
    return 1n;
  }
  let result = 1n;
  while (b > 0n) {
    if (b % 2n === 1n) {
      result = (result * a) % m;
    }
    a = (a * a) % m;
    b /= 2n;
  }
  return result;
}
function isPrime(n, k = 10) {
  if (n <= 1n)
    return false;
  if (n <= 3n)
    return true;
  let r = 0n;
  let d = n - 1n;
  while (d % 2n === 0n) {
    r++;
    d /= 2n;
  }
  for (let i = 0; i < k; i++) {
    const a = getRandomInt(2, Number(n - 2n));
    let x = modPow(BigInt(a), d, n);
    if (x === 1n || x === n - 1n)
      continue;
    for (let j = 0n; j < r - 1n; j++) {
      x = x ** 2n % n;
      if (x === n - 1n)
        break;
    }
    if (x !== n - 1n)
      return false;
  }
  return true;
}

console.log(
  "57は素数" + ( isPrime( BigInt(57) ) ? "です" : "ではありません" )
);

そして最後の工夫は、処理をメインスレッドではなくWebWorkerに任せている点です。

クライアントサイドのJavaScriptは通常、常に同期的に実行されるため、重い処理などを行うとユーザーの操作をブロッキングすることがあります。

素因数分解のような大量の計算を必要とする処理はメインスレッドに向いていないため、WebWorkerにより独立したタスクとして処理し、その結果や状況をmessageで送受信しています。

これにより、高速で処理が行える上に、ユーザーの操作をブロッキングせず進歩状況を表示できます。

余談。現代の社会で多く用いられている規格「RSA暗号」では、約308～309桁(10進法表記)の素数が利用されています。

私の環境(CPU: i9 12900K, Mem: 96GB)では、1秒間にmod計算が556万回を行えますが、この速度では最低でも数億年の計算が必要です。

しかし、現在研究段階である量子コンピュータが実現すれば、いつか解かれてしまうのかもしれないと言われています。