Jazone
GripNews🌘 針對有限位元寬度的確定性素性測試
➤ 從機率隨機到精確確定：32 位元整數的素性驗證策略
✤ https://www.jeremykun.com/2026/04/07/deterministic-miller-rabin/
本文探討瞭如何透過 Miller-Rabin 演算法進行確定性素數判斷。作者指出，雖然 Miller-Rabin 原始設計為機率演算法，但透過選擇特定的測試基底（Bases），可將其轉化為針對 32 位元整數的確定性測試。這種方法利用了強偽素數（Strong Pseudoprimes）的特性，僅需測試 {2, 3, 5, 7} 四個質數作為基底，即可確保 32 位元範圍內的判斷結果百分之百準確。文中不僅提供了 C++ 實作範例，亦討論了與其他高速素數篩選方法（如 primesieve）的效能差異。
+ 真是精簡優雅的實作，對於不需要處理超大質數的應用場景來說，這種確定性 Miller-Rabin 方法比引入複雜的素數篩選函式庫更輕量且直觀。
+ 這篇文章提醒了我們，選擇正確的「基底」對於測試的確定性至
#演算法 #程式設計 #數論 #Miller-Rabin
➤ 從機率隨機到精確確定：32 位元整數的素性驗證策略
✤ https://www.jeremykun.com/2026/04/07/deterministic-miller-rabin/
本文探討瞭如何透過 Miller-Rabin 演算法進行確定性素數判斷。作者指出，雖然 Miller-Rabin 原始設計為機率演算法，但透過選擇特定的測試基底（Bases），可將其轉化為針對 32 位元整數的確定性測試。這種方法利用了強偽素數（Strong Pseudoprimes）的特性，僅需測試 {2, 3, 5, 7} 四個質數作為基底，即可確保 32 位元範圍內的判斷結果百分之百準確。文中不僅提供了 C++ 實作範例，亦討論了與其他高速素數篩選方法（如 primesieve）的效能差異。
+ 真是精簡優雅的實作，對於不需要處理超大質數的應用場景來說，這種確定性 Miller-Rabin 方法比引入複雜的素數篩選函式庫更輕量且直觀。
+ 這篇文章提醒了我們，選擇正確的「基底」對於測試的確定性至
#演算法 #程式設計 #數論 #Miller-Rabin
Deterministic Primality Testing for Limited Bit Width
Problem: Determine if a 32-bit number is prime (deterministically) Solution: (in C++) // Bases to test. Using the first 4 prime bases makes the test deterministic // for all 32-bit integers. See https://oeis.org/A014233. int64_t bases[] = {2, 3, 5, 7}; inline int countTrailingZeros(uint64_t n) { if (n == 0) return 64; return __builtin_ctzll(n); } int64_t modularExponentiation(int64_t base, int64_t exponent, int64_t modulus) { int64_t res = 1; int64_t b = base % modulus; int64_t e = exponent; while (e > 0) { if (e & 1) { // Doesn't overflow because we assume 32-bit integer inputs res = (res * b) % modulus; } b = (b * b) % modulus; e >>= 1; } return res; } bool isPrime(int64_t n) { if (n < 2) return false; if (n < 4) return true; if (!
Ron Sparks
Kevin Stevens
Georgiann Baldino
Michael Fenichel
Robert H
novaTopFlex
