[問題案] Primarity Test

[SSRS-cp]

問題名: Primarity Test

問題

$Q$ クエリ

整数 $N$ が与えられるので、素数なら YES、そうでないなら NO と出力

制約

$1 \leq Q \leq 100,000$ $1 \leq N \leq 10^{18}$

[maspypy]

良さそうです。

[koba-e964]

Primality な気がします (二番目の r を l にする)

[SSRS-cp]

私が Issue 立てるときに勘違いしてました、すみません

[mizar]

参考

• Deterministic variants of the Miller-Rabin primality test

  • $N\lt 2^{32}$ の場合、 $\lbrace b_i \rbrace=\lbrace 2, 7, 61 \rbrace$ を底とした3回のMiller-Rabin素数テスト (底 $b_i\equiv 0\mod N$ の場合は除外して判定)
  • $N\lt 2^{64}$ の場合、 $\lbrace b_i \rbrace=\lbrace 2, 325, 9375, 28178, 450775, 9780504, 1795265022 \rbrace$ を底とした7回のMiller-Rabin素数テスト (底 $b_i\equiv 0\mod N$ の場合は除外して判定)

• Baillie-PSW素数判定法 実行例: https://judge.yosupo.jp/submission/139990

  • $\lbrace 2 \rbrace$ を底とした Miller-Rabin素数テスト + 強いLucas擬素数(Strong Lucas pseudoprime)テスト
  • OEIS:A001262 Strong pseudoprimes to base 2 : 底 $\lbrace 2 \rbrace$ の Miller-Rabin素数テスト で probably prime (おそらく素数) と判定される合成数 (擬素数)
  • OEIS:A217255 Strong Lucas pseudoprimes : 強いリュカ擬素数テストで probably prime (おそらく素数) と判定される合成数 (擬素数)
  • 何れの素数テストでも共に probably prime (おそらく素数) と判定される合成数が稀 (未発見?) であり、少なくとも $N\lt 2^{64}$ の範囲では存在しない。

• Forisek, Michal and Jakub Jancina. “Fast Primality Testing for Integers That Fit into a Machine Word.” Conference on Current Trends in Theory and Practice of Informatics (2015).

  • $N$ の値をハッシュ関数によって処理し、Miller-Rabin素数テストで範囲内の全ての合成数を漏れなく判定できる底の値をハッシュ表に登録しておくことで、 Miller-Rabin素数テストの実行回数・実行時間を削減できるとするpaper.
  • FJ32_256: $N\lt 2^{32}$ の時、 256要素のハッシュ表を用いて 底の値 $\lbrace b \rbrace$ を表引きし、 $\lbrace b \rbrace$ を底とする 1回のMiller-Rabin素数テストで素数判定するバリアント。 (paper内にソースコード有り)
  • FJ64_16k: $N\lt 2^{64}$ の時、 16384要素のハッシュ表を用いて 底の値 (ハッシュ表の各要素は2個の底の値 $\lbrace b_1, b_2 \rbrace$ をpackしている) を表引きし、 $\lbrace 2, b_1, b_2 \rbrace$ を底とする 3回の Miller-Rabin素数テストで素数判定するバリアント。 実行例: https://judge.yosupo.jp/submission/140049
  • FJ64_262k: $N\lt 2^{64}$ の時、 262144要素のハッシュ表を用いて 底の値 $\lbrace b \rbrace$ を表引きし、 $\lbrace 2, b \rbrace$ を底とする 2回の Miller-Rabin素数テストで素数判定するバリアント。 実行例: https://judge.yosupo.jp/submission/139998
  • ソースコード: https://people.ksp.sk/~misof/primes/

• yukicoder: No.3030 ミラー・ラビン素数判定法のテスト 素数判定 9.93sec 制約: $n\leq 10^4, x_i\lt 2^{63}$

• Library Checker: Primality Test 素数判定 5sec 制約: $Q\leq 10^5, n_i\leq 10^{18}$

• Library Checker: Factolize 素因数分解 10sec 制約: $Q\leq 100, a_i\leq 10^{18}$

• Mojacoder: mizar/素数判定 (64bit) 素数判定 2sec 制約: $Q\leq 10^4, a_i\lt 2^{64}$

• zenn: mizar/64bit数の素数判定

[maspypy]

https://drive.google.com/file/d/1ytqMuPhmxhE2loMZL1HOJ3l2iaLCv4tz