pratts module

Pure-Python library that enables generation and verification of Pratt certificates for prime numbers.

pratts(argument, primes=None, partial=False)

Build a Pratt certificate for the supplied integer argument and the accompanying iterable of prime factors.

Parameters:

• argument (int) – The prime number for which to generate a certificate.

• primes (Union[Iterable[int], Callable[[int], Iterable[int]]]) – List of – or a function that returns – prime factors.

• partial (bool) – Flag to allow generation of a best-effort partial certificate.

Return type:

Optional[Dict[int, Optional[Sequence[int]]]]

This function returns a dictionary in which the keys consist of all primes p for which a certificate was found during the process of generating the certificate for the argument (including the argument itself). Each key is associated with the list of prime factors of p - 1 (such that every prime factor in these lists also appears as a key in the dictionary).

>>> pratts(2)
{2: []}
>>> pratts(3, [2])
{2: [], 3: [2]}
>>> pratts(5, [2])
{2: [], 5: [2]}
>>> pratts(7, [2, 3])
{2: [], 3: [2], 7: [2, 3]}
>>> pratts(11, [2, 5])
{2: [], 5: [2], 11: [2, 5]}
>>> pratts(41, [2, 5])
{2: [], 5: [2], 41: [2, 5]}
>>> pratts(241, [2, 3, 5])
{2: [], 3: [2], 5: [2], 241: [2, 3, 5]}
>>> pratts(257, [2])
{2: [], 257: [2]}

It is also possible to supply a function that returns all prime factors of its integer input (as an iterable of integers). Note that this function must return its input as one of the factors of that input.

>>> pratts(241, lambda n: [k for k in range(2, n + 1) if n % k == 0])
{2: [], 3: [2], 5: [2], 241: [2, 3, 5]}

An exception is raised If the supplied function behaves incorrectly.

>>> pratts(241, lambda n: 1)
Traceback (most recent call last):
  ...
RuntimeError: primes parameter callable must return an iterable
>>> pratts(241, lambda n: ['abc'])
Traceback (most recent call last):
  ...
RuntimeError: primes parameter callable must return integers
>>> pratts(241, lambda n: [-1])
Traceback (most recent call last):
  ...
RuntimeError: primes parameter callable must return positive integers

An example involving a larger prime is presented below.

>>> certificate = pratts(
...     1011235813471123581347,
...     [
...         2, 3, 5, 7, 11, 17, 19, 31, 97, 229, 251, 463, 5953,
...         44449, 177797, 250027, 206955709, 8830800103031
...     ]
... )
>>> from pprint import pprint
>>> pprint(certificate)
{2: [],
 3: [2],
 5: [2],
 7: [2, 3],
 11: [2, 5],
 17: [2],
 19: [2, 3],
 31: [2, 3, 5],
 97: [2, 3],
 229: [2, 3, 19],
 251: [2, 5],
 463: [2, 3, 7, 11],
 5953: [2, 3, 31],
 44449: [2, 3, 463],
 177797: [2, 44449],
 250027: [2, 3, 7, 5953],
 206955709: [2, 3, 97, 177797],
 8830800103031: [2, 5, 17, 251, 206955709],
 1011235813471123581347: [2, 229, 250027, 8830800103031]}

A certificate can be verified by supplying its keys to this function.

>>> pratts(1011235813471123581347, certificate.keys()) is not None
True

If the partial parameter is True, then a partial certificate may be returned if a complete certificate could not be generated. In particular, any key p for which a prime factorization of p - 1 could not be determined is associated with None in the certificate.

>>> pratts(241, [2, 5], True)
{2: [], 5: [2], 241: None}
>>> pratts(1011235813471123581347, [], True)
{1011235813471123581347: None}

When supplied an input that can be determined to be composite, None is returned.

>>> pratts(4, [2, 3]) is None
True
>>> pratts(6, [2, 5]) is None
True
>>> pratts(24, [2, 5, 11, 23]) is None
True

If the supplied input does not contain sufficiently many primes to obtain all the prime factorizations necessary to build a certificate, then an exception is raised (which also specifies at least one example of a p - 1 term that could not be factored).

>>> pratts(3, [])
Traceback (most recent call last):
  ...
RuntimeError: cannot find all prime factors for 2
>>> pratts(1011235813471123581347, [8830800103031])
Traceback (most recent call last):
  ...
RuntimeError: cannot find all prime factors for 8830800103030
>>> pratts(1011235813471123581347)
Traceback (most recent call last):
  ...
RuntimeError: cannot find all prime factors for 1011235813471123581346
>>> pratts(24)
Traceback (most recent call last):
  ...
RuntimeError: cannot find all prime factors for 23

An exception is raised if any of the supplied arguments are not valid.

>>> pratts('abc')
Traceback (most recent call last):
  ...
TypeError: argument must be an integer
>>> pratts(-123)
Traceback (most recent call last):
  ...
ValueError: argument must be a positive integer
>>> pratts(3, primes=2)
Traceback (most recent call last):
  ...
TypeError: primes parameter must be an iterable or callable
>>> pratts(3, ['abc'])
Traceback (most recent call last):
  ...
ValueError: every prime factor must be an integer
>>> pratts(3, [1])
Traceback (most recent call last):
  ...
ValueError: every prime factor must be greater than 1
>>> pratts(25, [6])
Traceback (most recent call last):
  ...
RuntimeError: cannot find all prime factors for 5