# miller-rabin

Published articles for miller-rabin.

This is one page of public article previews, not the complete archive. Follow Next page to continue. Summaries are not the original full articles.

## Deterministic Primality Testing for Limited Bit Width

DevFeed: [Deterministic Primality Testing for Limited Bit Width](<https://devfeed.tech/articles/deterministic-primality-testing-for-limited-bit-width-40494.md>)

Original publisher: [Read original article](<https://www.jeremykun.com/2026/04/07/deterministic-miller-rabin/>)

Published: 2026-04-07T13:00:00Z

Content type: tutorial

Language: en

Sources: [Jeremy Kun](<https://devfeed.tech/sources/jeremy-kun.md>)

Topics: [Algorithms](<https://devfeed.tech/topics/algorithms.md>), [C++](<https://devfeed.tech/topics/c-plus-plus.md>), [Mathematics](<https://devfeed.tech/topics/mathematics.md>), [Cryptography](<https://devfeed.tech/topics/cryptography.md>), [homomorphic encryption](<https://devfeed.tech/topics/homomorphic-encryption.md>)

Tags: [algorithm](<https://devfeed.tech/tags/algorithm.md>), [c-plus-plus](<https://devfeed.tech/tags/c-plus-plus.md>), [code](<https://devfeed.tech/tags/code.md>), [cryptography](<https://devfeed.tech/tags/cryptography.md>), [homomorphic-encryption](<https://devfeed.tech/tags/homomorphic-encryption.md>), [mathematics](<https://devfeed.tech/tags/mathematics.md>), [miller-rabin](<https://devfeed.tech/tags/miller-rabin.md>), [oeis](<https://devfeed.tech/tags/oeis.md>), [primes](<https://devfeed.tech/tags/primes.md>), [programming](<https://devfeed.tech/tags/programming.md>), [randomized-algorithm](<https://devfeed.tech/tags/randomized-algorithm.md>)

### AI overview

This article explains how to perform deterministic Miller-Rabin primality testing for 32-bit integers. It presents C++ code using the bases 2, 3, 5, and 7, which the article states is deterministic for all 32-bit inputs, and discusses strong pseudoprimes and related research.

### Source excerpt

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 (!

## Miller-Rabin Primality Test

DevFeed: [Miller-Rabin Primality Test](<https://devfeed.tech/articles/miller-rabin-primality-test-40323.md>)

Original publisher: [Read original article](<https://www.jeremykun.com/2013/06/16/miller-rabin-primality-test/>)

Published: 2013-06-16T18:55:40Z

Content type: tutorial

Language: en

Sources: [Jeremy Kun](<https://devfeed.tech/sources/jeremy-kun.md>)

Topics: [Python](<https://devfeed.tech/topics/python.md>), [Algorithms](<https://devfeed.tech/topics/algorithms.md>), [Algorithms, Complexity](<https://devfeed.tech/topics/algorithms-complexity.md>), [Cryptography](<https://devfeed.tech/topics/cryptography.md>)

Tags: [algorithm](<https://devfeed.tech/tags/algorithm.md>), [algorithms](<https://devfeed.tech/tags/algorithms.md>), [complexity-theory](<https://devfeed.tech/tags/complexity-theory.md>), [computational-complexity](<https://devfeed.tech/tags/computational-complexity.md>), [cryptography](<https://devfeed.tech/tags/cryptography.md>), [miller-rabin](<https://devfeed.tech/tags/miller-rabin.md>), [primes](<https://devfeed.tech/tags/primes.md>), [probabilistic](<https://devfeed.tech/tags/probabilistic.md>), [programming](<https://devfeed.tech/tags/programming.md>), [python](<https://devfeed.tech/tags/python.md>), [random-number-generators](<https://devfeed.tech/tags/random-number-generators.md>), [randomized-algorithm](<https://devfeed.tech/tags/randomized-algorithm.md>), [rsa](<https://devfeed.tech/tags/rsa.md>)

### AI overview

This tutorial explains the Miller-Rabin primality test, including its probabilistic error bound, Python implementation, and role in testing whether numbers are prime. It also discusses the algorithm's relevance to cryptography and complexity theory.

### Source excerpt

Problem: Determine if a number is prime, with an acceptably small error rate. Solution: (in Python) import random def decompose(n): exponentOfTwo = 0 while n % 2 == 0: n = n/2 exponentOfTwo += 1 return exponentOfTwo, n def isWitness(possibleWitness, p, exponent, remainder): possibleWitness = pow(possibleWitness, remainder, p) if possibleWitness == 1 or possibleWitness == p - 1: return False for _ in range(exponent): possibleWitness = pow(possibleWitness, 2, p) if possibleWitness == p - 1: return False return True def probablyPrime(p, accuracy=100): if p == 2 or p == 3: return True if p < 2: return False exponent, remainder = decompose(p - 1) for _ in range(accuracy): possibleWitness = random.