rabinmiller module

Pure-Python implementation of the Rabin-Miller primality test.

rabinmiller(number, rounds=10)

Pure-Python implementation of the Rabin-Miller primality test.

Parameters:

• number (int) – Nonnegative integer to be tested for primality.

• rounds (int) – Number of random base values to consider when testing.

Return type:

bool

The Rabin-Miller primality test may return a false positive with low probability, but never returns a false negative. A return value of False guarantees that the input is composite; a return value of True indicates that there is a high likelihood that the input is prime.

>>> rabinmiller(2)
True
>>> rabinmiller(4)
False
>>> rabinmiller(9999777777776655544433333333222111111111)
True
>>> rabinmiller(9999777777776655544433333333222111111115)
False
>>> rabinmiller(int(''.join([
...     '129600000000000000000000000000060069996000000000000000',
...     '0000000092808755643600000000000000000004779682424746201'
... ])))
False
>>> rabinmiller(0) or rabinmiller(1)
False
>>> any(rabinmiller(i * i) for i in range(2, 1000))
False

Two optimizations are implemented: 16-bit inputs are checked using a hash-based lookup and all inputs are checked explicitly against all 16-bit factors.

Any attempt to invoke this function with an argument that does not have the expected types (or does not fall within the supported range) raises an exception.

>>> rabinmiller('abc')
Traceback (most recent call last):
  ...
TypeError: number must be an integer
>>> rabinmiller(-123)
Traceback (most recent call last):
  ...
ValueError: number must be a nonnegative integer
>>> rabinmiller(123, 'abc')
Traceback (most recent call last):
  ...
TypeError: number of rounds must be an integer
>>> rabinmiller(123, 0)
Traceback (most recent call last):
  ...
ValueError: number of rounds must be a positive integer