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
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
Summary not yet generated for this article.
Comments (4 of ) ⌛