JavaScriptで巨大な数が素数であるか判定したい

Question

実現したいこと

JavaScriptで巨大な数(メルセンヌ数)が素数であるか判定したいです。
巨大な数とは、具体的には 2^100000000 (10進法表記で約3000万桁) 程度です。

前提

JavaScript V8 11.1.24.7

let prime, n;
for (n = 100000000n; ; n++) {

  // 一度目のループ
  // 2^n - 1 を計算する
  if (!prime) prime = (2n ** n) - 1n;
  // 2回目以降のループ
  // 2^n - 1 を計算するとリソースを食うので、
  // 一つ前の計算で求めた結果に1を足して2を掛けて1を引く
  else prime = (prime + 1n) * 2n - 1n;

  // 素数判定
  if (IsPrime(n, prime))
    console.log("2^" + primejs.n + "-1 は素数です。");
}

function IsPrime(n, num) {
  // 高速化のため、素数番目以外のメルセンヌ数は除外
  // 省略

  // リュカ–レーマーのテスト
  let s = 4n, M = (1n << num) - 1n;
  for (let n = 2; n < num; n++)
    s = (s ** 2n - 2n) % M;

  if (s != 0n) return false;

  // 素数の場合の処理
  return true;
}

発生している問題・エラーメッセージ

Uncaught RangeError: Maximum BigInt size exceeded
発生場所: `let s = 4n, M = (1n << num) - 1n;`

試したこと

リュカ–レーマーのテストを用いずに、単純に2からsqrt(num)までmodを行うと数がオーバーしません。

function sqrt(value) {
  let sqrt = value / 3n;
  if (value <= 0n) return 0n;
  for (let i = 0; i < 6; i++)
    sqrt = (sqrt + value / sqrt) / 2n;
  return sqrt;
}
function IsPrime(n, num) {
  // 3以上かつ数字の平方根より小さい数で割り切れないか試す。numRoot mod n === 0 の時点で終了  
  // BigIntは小数点以下を扱わないため、Math.ceilは不要
  let numRoot = sqrt(num);
  for (let i = BigInt(3); i < numRoot; i++)
  if (num % i === 0n) return false;

  return true;
}

しかし、それでは最大でsqrt(num)-2回のループ処理が必要となってしまうため、どうしてもリュカ–レーマーのテストをオーバーフローさせずに実行したいです。

そこで、BigIntの上限より大きな数を扱う方法若しくは巨大な数を登場させずに素数判定ができるアルゴリズムがあれば教えて頂きたいです。

宜しくお願いします。

Comments

[Zuishin]

> しかし、それでは最大でsqrt(num)-2回のループ処理が必要となってしまうため、どうしてもリュカ–レーマーのテストをオーバーフローさせずに実行したいです。

つまり、それより速い方法があると思っていますか？

[Zuishin]

上のコメントは「リュカ・レーマーの判定法を用いず判定したい」と読んでしまったためです。
判定法を正しく実装したいということなら、BigInt を使わない方法を探すのが良いでしょう。
単純に、多倍長整数を自分で実装してしまえば解決するかもしれません。
JavaScript ではなく C++ の方がみつけやすいと思います。

[ActiveTK]

コメント有難うございます。
そもそもJavaScriptには実行メモリ制限があるため、C#でBigIntegerを用いて同様の処理を実装したことにより、自己解決(解決なのかは未知数)しました。

[Zuishin]

過去の質問から見て想定していた結果と寸分違わず一致しました。

Answer 1

そもそもJavaScriptには実行メモリ制限があるなど巨大な数字の処理に向いていないため、
C#でBigIntegerを用いて同様の処理を実装したことにより、自己解決しました。

using System.Numerics;

static bool IsPrime(BigInteger n)
{
        if (n < 2)
            return false;
        if (n != 2 && n % 2 == 0)
        {
            return false;
        }
        Random rand = new Random();
        for (int i = 0; i < 30; i++)
        {
            BigInteger a = new BigInteger();
            do
            {
                a = BigInteger.Remainder(BigInteger.Abs(new BigInteger(rand.Next())), n);
            } while (a == 0);
            BigInteger x = BigInteger.ModPow(a, n - 1, n);
            if (x != 1)
                return false;
        }
        return true;
}