# 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.