Skip to main content

Fast, deterministic* Miller-Rabin primality test.

Project description

miller-rabin

PyPI Python 3.6+ CPython only License: MIT Test Docs Code style: black

I implement this fast (see Performance), deterministic (up to 64 bits unsigned), permissively licensed (MIT) Miller-Rabin primality test as a C extension to Python so you don't have to.

Only CPython 3.6 or later is supported.

Project canonical URL: https://github.com/zmwangx/miller-rabin

Algorithm

This library implements Bradley Berg's deterministic variant[1] of the Miller-Rabin primality test for 64-bit unsigned integers as recommended by [2], and the usual probablistic test for integers beyond 64-bit. Preliminary tests with small prime divisions and in some cases one pass of Fermat test are inspired by boost::multiprecision::miller_rabin_test[3]. Integers within 16-bit are directly checked against a lookup table.

GMP[4] is used for modular exponentiation, hence the library links to libgmp (LGPLv3).

Credit:

Installation

pip install miller-rabin

Wheels with dependencies included are available for macOS and Linux (manylinux1, manylinux2010 and manylinux2014) for Python 3.6, 3.7 and 3.8. A reasonably recent pip should be able to pick a wheel automatically (manylinux1 support was added in v8.1.2), but it is advised to update pip to latest.

To install from a source distribution, CPython development headers and libgmp along with development headers are required.

API

The API is extremely simple so there's no need for a separate Sphinx doc site.

NAME
    miller_rabin - Fast, deterministic* Miller-Rabin primality test.

FUNCTIONS
    miller_rabin(n, k=10, /)
        Perform Miller-Rabin primality test on the arbitrary precision int.

        A deterministic variant is auto-selected if n fits into 64-bit unsigned;
        otherwise, the probablistic variant is used, and k determines the number of
        test rounds to perform.

    miller_rabin_deterministic32(n, /)
        Perform deterministic Miller-Rabin primality test on the 32-bit unsigned int.

    miller_rabin_deterministic64(n, /)
        Perform deterministic Miller-Rabin primality test on the 64-bit unsigned int.

In practice you should simply use the miller_rabin function for all numbers regardless of bit count, unless you want to enforce the bit count without checking beforehand.

Performance

TL;DR: This library can deterministically test ~2.5 million odd 64-bit unsigned integers per second on a 3.7GHz Intel Core i5 CPU (single thread).

Below are some benchmarks of this library's primality test vs that of gmpy2 (Python binding to GMP). The first column is the bit count of each random sample (random odd numbers in the given range), and results are in million tests per second, estimated from the total run time on a random sample of size one million. Results labeled MR are for miller_rabin.miller_rabin from this library; results labeled G(25) are for gmpy2.is_prime on default setting (25 rounds); results labeled G(10) are for gmpy2.is_prime with 10 rounds (comparable to this library's default for numbers above 64-bit). Note that gmpy2.is_prime uses mpz_probab_prime_p under the hood. See bench/benchmark.py for details.

#bits	MR	G(25)	G(10)
1-32	4.538	0.901	1.581
32	4.553	0.916	1.601
1-64	2.597	0.845	1.377
64	2.500	0.755	1.258
65	1.120	0.694	1.153
96	1.044	0.642	0.977
128	0.832	0.495	0.745
256	0.327	0.204	0.286
(unit: million tests per second)
(CPU: Intel(R) Core(TM) i5-9600K CPU @ 3.70GHz)
#bits	MR	G(25)	G(10)
1-32	3.275	0.960	1.530
32	3.288	0.982	1.561
1-64	2.026	0.865	1.315
64	1.933	0.743	1.176
65	0.915	0.727	1.129
96	0.878	0.680	0.983
128	0.663	0.507	0.735
256	0.258	0.180	0.254
(unit: million tests per second)
(CPU: Intel(R) Core(TM) i7-8700B CPU @ 3.20GHz)

(All benchmarks are single-thread.)

As we can see, this library is 50-200% faster than gmpy2 in addition to being deterministic for unsigned 64-bit integers, depending on CPU. For integers just above 64 bits, depending on CPU this library may be up to 20% slower than gmpy2.is_prime at 10 rounds, but the gap is closed as numbers get larger, and eventually this library is faster again.

Note that for 64-bit unsigned integers, there is a pure Python implementation in alt/miller_rabin.py as a demonstration (actually, it still uses gmpy2's mpz type for modular exponentiation, so it's not pure Python strictly speaking; the reason is that CPython's long_pow can be >20x slower than GMP's mpz_powm even just for unsigned 64-bit integers). It is way slower than this library, so a C extension is indeed necessary.

Development

Argument handling code is automatically generated by Argument Clinic from the latest v3.6.x release tree (for compatibility).

$ cd /path/to/cpython/dev/tree
$ git checkout v3.6.x
$ python3 Tools/clinic/clinic.py -f /path/to/miller-rabin/src/miller-rabin.c

Contributing

Contributions are welcome. Algorithmic changes should demonstrate measurable performance improvements (using bench/benchmark.py).

Ideas:

  • Maybe a Montgomery multiplication implementation could be faster than mpz_powm? Perl's Math::Prime::Util implements Montgomery multiplication in montmath.h and uses it for Miller-Rabin, but the implementation is in x64 asm which I'm not comfortable with (could be necessary though), and the code is unfortunately GPL.

  • I'm not too keen on figuring out static wheel building on Windows, so contribution from experienced Windows developer is welcome here. See .github/workflows/build-and-publish-distributions.yml.

Project details


Download files

Download the file for your platform. If you're not sure which to choose, learn more about installing packages.

Source Distribution

miller_rabin-1.0.1.tar.gz (68.6 kB view details)

Uploaded Source

Built Distributions

miller_rabin-1.0.1-cp38-cp38-manylinux2014_x86_64.whl (331.7 kB view details)

Uploaded CPython 3.8

miller_rabin-1.0.1-cp38-cp38-manylinux2010_x86_64.whl (332.6 kB view details)

Uploaded CPython 3.8manylinux: glibc 2.12+ x86-64

miller_rabin-1.0.1-cp38-cp38-manylinux1_x86_64.whl (330.5 kB view details)

Uploaded CPython 3.8

miller_rabin-1.0.1-cp38-cp38-macosx_10_13_x86_64.whl (131.6 kB view details)

Uploaded CPython 3.8macOS 10.13+ x86-64

miller_rabin-1.0.1-cp37-cp37m-manylinux2014_x86_64.whl (331.8 kB view details)

Uploaded CPython 3.7m

miller_rabin-1.0.1-cp37-cp37m-manylinux2010_x86_64.whl (332.6 kB view details)

Uploaded CPython 3.7mmanylinux: glibc 2.12+ x86-64

miller_rabin-1.0.1-cp37-cp37m-manylinux1_x86_64.whl (330.5 kB view details)

Uploaded CPython 3.7m

miller_rabin-1.0.1-cp37-cp37m-macosx_10_13_x86_64.whl (131.6 kB view details)

Uploaded CPython 3.7mmacOS 10.13+ x86-64

miller_rabin-1.0.1-cp36-cp36m-manylinux2014_x86_64.whl (330.9 kB view details)

Uploaded CPython 3.6m

miller_rabin-1.0.1-cp36-cp36m-manylinux2010_x86_64.whl (331.7 kB view details)

Uploaded CPython 3.6mmanylinux: glibc 2.12+ x86-64

miller_rabin-1.0.1-cp36-cp36m-manylinux1_x86_64.whl (330.1 kB view details)

Uploaded CPython 3.6m

miller_rabin-1.0.1-cp36-cp36m-macosx_10_13_x86_64.whl (131.6 kB view details)

Uploaded CPython 3.6mmacOS 10.13+ x86-64

File details

Details for the file miller_rabin-1.0.1.tar.gz.

File metadata

  • Download URL: miller_rabin-1.0.1.tar.gz
  • Upload date:
  • Size: 68.6 kB
  • Tags: Source
  • Uploaded using Trusted Publishing? No
  • Uploaded via: twine/3.1.1 pkginfo/1.5.0.1 requests/2.23.0 setuptools/46.1.3 requests-toolbelt/0.9.1 tqdm/4.44.1 CPython/3.7.7

File hashes

Hashes for miller_rabin-1.0.1.tar.gz
Algorithm Hash digest
SHA256 0ba0ab6cddb4ee6f9bdf829b66b7bb8e363ce5fdb80241528e461c667816a926
MD5 9ef5b146f37454b784ba3f5d02afcd81
BLAKE2b-256 fb761381ddc726f59fdb7af9ebc4926e37d9d010fe711d8ade15c1499e0b61f3

See more details on using hashes here.

File details

Details for the file miller_rabin-1.0.1-cp38-cp38-manylinux2014_x86_64.whl.

File metadata

  • Download URL: miller_rabin-1.0.1-cp38-cp38-manylinux2014_x86_64.whl
  • Upload date:
  • Size: 331.7 kB
  • Tags: CPython 3.8
  • Uploaded using Trusted Publishing? No
  • Uploaded via: twine/3.1.1 pkginfo/1.5.0.1 requests/2.23.0 setuptools/46.1.3 requests-toolbelt/0.9.1 tqdm/4.44.1 CPython/3.7.7

File hashes

Hashes for miller_rabin-1.0.1-cp38-cp38-manylinux2014_x86_64.whl
Algorithm Hash digest
SHA256 9c74ec3beada408b857d3eaaedfa8170535dd5533cceb001b1d186a5473664b5
MD5 30fd16992e0fa7d89af1e9c11774fd29
BLAKE2b-256 465b884bec070ab6c6b2a6bb0d3327fbde511d84e42ee067dd67e9add9d70f8b

See more details on using hashes here.

File details

Details for the file miller_rabin-1.0.1-cp38-cp38-manylinux2010_x86_64.whl.

File metadata

  • Download URL: miller_rabin-1.0.1-cp38-cp38-manylinux2010_x86_64.whl
  • Upload date:
  • Size: 332.6 kB
  • Tags: CPython 3.8, manylinux: glibc 2.12+ x86-64
  • Uploaded using Trusted Publishing? No
  • Uploaded via: twine/3.1.1 pkginfo/1.5.0.1 requests/2.23.0 setuptools/46.1.3 requests-toolbelt/0.9.1 tqdm/4.44.1 CPython/3.7.7

File hashes

Hashes for miller_rabin-1.0.1-cp38-cp38-manylinux2010_x86_64.whl
Algorithm Hash digest
SHA256 d632213b1b6714834976ddf0fe9d44d5d0095f703dcdfae2fd16718f44d83da4
MD5 1990a1189d38435810dcaa90d2c242da
BLAKE2b-256 cc534704d196bc83a48181263f0bf79ed2b40e7016dcb32c6de834a5d8518f7e

See more details on using hashes here.

File details

Details for the file miller_rabin-1.0.1-cp38-cp38-manylinux1_x86_64.whl.

File metadata

  • Download URL: miller_rabin-1.0.1-cp38-cp38-manylinux1_x86_64.whl
  • Upload date:
  • Size: 330.5 kB
  • Tags: CPython 3.8
  • Uploaded using Trusted Publishing? No
  • Uploaded via: twine/3.1.1 pkginfo/1.5.0.1 requests/2.23.0 setuptools/46.1.3 requests-toolbelt/0.9.1 tqdm/4.44.1 CPython/3.7.7

File hashes

Hashes for miller_rabin-1.0.1-cp38-cp38-manylinux1_x86_64.whl
Algorithm Hash digest
SHA256 e20d2af1542f9aad458b98f517dfc57ac36c23b332dabf73d204d82a18595b62
MD5 e0d9d204bc21fb5ee6a20b5ffa19fcf5
BLAKE2b-256 05a46f3e3fdae652baf0b4cffc804ecee2617b27adbc2680e158f0d455809765

See more details on using hashes here.

File details

Details for the file miller_rabin-1.0.1-cp38-cp38-macosx_10_13_x86_64.whl.

File metadata

  • Download URL: miller_rabin-1.0.1-cp38-cp38-macosx_10_13_x86_64.whl
  • Upload date:
  • Size: 131.6 kB
  • Tags: CPython 3.8, macOS 10.13+ x86-64
  • Uploaded using Trusted Publishing? No
  • Uploaded via: twine/3.1.1 pkginfo/1.5.0.1 requests/2.23.0 setuptools/46.1.3 requests-toolbelt/0.9.1 tqdm/4.44.1 CPython/3.7.7

File hashes

Hashes for miller_rabin-1.0.1-cp38-cp38-macosx_10_13_x86_64.whl
Algorithm Hash digest
SHA256 6a055935ad75bfdbb175d1b74b7a03ab0cd28881322ffe662b932f2043871ebe
MD5 3de185ede763c4395596eaf424943007
BLAKE2b-256 64f80eede47e5f2d1bec429d35a9cc3e40a340e6cde150f22b94e05dd70e9ed2

See more details on using hashes here.

File details

Details for the file miller_rabin-1.0.1-cp37-cp37m-manylinux2014_x86_64.whl.

File metadata

  • Download URL: miller_rabin-1.0.1-cp37-cp37m-manylinux2014_x86_64.whl
  • Upload date:
  • Size: 331.8 kB
  • Tags: CPython 3.7m
  • Uploaded using Trusted Publishing? No
  • Uploaded via: twine/3.1.1 pkginfo/1.5.0.1 requests/2.23.0 setuptools/46.1.3 requests-toolbelt/0.9.1 tqdm/4.44.1 CPython/3.7.7

File hashes

Hashes for miller_rabin-1.0.1-cp37-cp37m-manylinux2014_x86_64.whl
Algorithm Hash digest
SHA256 934d77f62d52420cdd83b0d9108d98db35369cd58c4d72288487b291ab4f71c3
MD5 e6fbfbd3a461b42db49691eb0c7be6ae
BLAKE2b-256 25e20440ce352d55c23ea0e1c695d5172451f8143eafee5744391b9ba488af1d

See more details on using hashes here.

File details

Details for the file miller_rabin-1.0.1-cp37-cp37m-manylinux2010_x86_64.whl.

File metadata

  • Download URL: miller_rabin-1.0.1-cp37-cp37m-manylinux2010_x86_64.whl
  • Upload date:
  • Size: 332.6 kB
  • Tags: CPython 3.7m, manylinux: glibc 2.12+ x86-64
  • Uploaded using Trusted Publishing? No
  • Uploaded via: twine/3.1.1 pkginfo/1.5.0.1 requests/2.23.0 setuptools/46.1.3 requests-toolbelt/0.9.1 tqdm/4.44.1 CPython/3.7.7

File hashes

Hashes for miller_rabin-1.0.1-cp37-cp37m-manylinux2010_x86_64.whl
Algorithm Hash digest
SHA256 61921833b426c35c33aabcb1b8ddc8425a9bfe83dd9d157fb957be4e05a5c120
MD5 1aa3c2c454fc7093bc197f360fd711d4
BLAKE2b-256 4e5fd4cdd5edcf6da17ec006ba5ee2cb2a4061b4b643f1ce00c3be1b0095e6b3

See more details on using hashes here.

File details

Details for the file miller_rabin-1.0.1-cp37-cp37m-manylinux1_x86_64.whl.

File metadata

  • Download URL: miller_rabin-1.0.1-cp37-cp37m-manylinux1_x86_64.whl
  • Upload date:
  • Size: 330.5 kB
  • Tags: CPython 3.7m
  • Uploaded using Trusted Publishing? No
  • Uploaded via: twine/3.1.1 pkginfo/1.5.0.1 requests/2.23.0 setuptools/46.1.3 requests-toolbelt/0.9.1 tqdm/4.44.1 CPython/3.7.7

File hashes

Hashes for miller_rabin-1.0.1-cp37-cp37m-manylinux1_x86_64.whl
Algorithm Hash digest
SHA256 df499a778b7f2391bc17485bf54b4af0a198d7e9a0b6a88bd192bffe934ecdf1
MD5 35afaf70c2e04760235262ed5799a74a
BLAKE2b-256 f63c1ec3fed6c37c61125fba34e0c645a2bf71c287c520301490dc895e281d18

See more details on using hashes here.

File details

Details for the file miller_rabin-1.0.1-cp37-cp37m-macosx_10_13_x86_64.whl.

File metadata

  • Download URL: miller_rabin-1.0.1-cp37-cp37m-macosx_10_13_x86_64.whl
  • Upload date:
  • Size: 131.6 kB
  • Tags: CPython 3.7m, macOS 10.13+ x86-64
  • Uploaded using Trusted Publishing? No
  • Uploaded via: twine/3.1.1 pkginfo/1.5.0.1 requests/2.23.0 setuptools/46.1.3 requests-toolbelt/0.9.1 tqdm/4.44.1 CPython/3.7.7

File hashes

Hashes for miller_rabin-1.0.1-cp37-cp37m-macosx_10_13_x86_64.whl
Algorithm Hash digest
SHA256 78c22b46490300473813b46606ddc1ee984b1398f72ca147a88332590b202036
MD5 c6163a25feca7f94fa82f7b48c50f38e
BLAKE2b-256 3c6ce1fe227caaaab7f917643cbb3b50a86ba2ce6f096df6c430ffbcb3c03341

See more details on using hashes here.

File details

Details for the file miller_rabin-1.0.1-cp36-cp36m-manylinux2014_x86_64.whl.

File metadata

  • Download URL: miller_rabin-1.0.1-cp36-cp36m-manylinux2014_x86_64.whl
  • Upload date:
  • Size: 330.9 kB
  • Tags: CPython 3.6m
  • Uploaded using Trusted Publishing? No
  • Uploaded via: twine/3.1.1 pkginfo/1.5.0.1 requests/2.23.0 setuptools/46.1.3 requests-toolbelt/0.9.1 tqdm/4.44.1 CPython/3.7.7

File hashes

Hashes for miller_rabin-1.0.1-cp36-cp36m-manylinux2014_x86_64.whl
Algorithm Hash digest
SHA256 4e4ef6eae9c7f1b4c55085a31ccd03ef8a0b64e864893a51ba462239571db3a2
MD5 741bf56a94323e05d673a92b05f7e0a7
BLAKE2b-256 c495ccf08c225074296abcf0bbfad23b2998ac4842f0398604a8bbe61100dd82

See more details on using hashes here.

File details

Details for the file miller_rabin-1.0.1-cp36-cp36m-manylinux2010_x86_64.whl.

File metadata

  • Download URL: miller_rabin-1.0.1-cp36-cp36m-manylinux2010_x86_64.whl
  • Upload date:
  • Size: 331.7 kB
  • Tags: CPython 3.6m, manylinux: glibc 2.12+ x86-64
  • Uploaded using Trusted Publishing? No
  • Uploaded via: twine/3.1.1 pkginfo/1.5.0.1 requests/2.23.0 setuptools/46.1.3 requests-toolbelt/0.9.1 tqdm/4.44.1 CPython/3.7.7

File hashes

Hashes for miller_rabin-1.0.1-cp36-cp36m-manylinux2010_x86_64.whl
Algorithm Hash digest
SHA256 3c6fb019bd4b2a34dadb3640eff5d927f4e63c05ab9fd56140a93407e9c00a18
MD5 cd3c515c170ac6f48f2b44b3a771c13f
BLAKE2b-256 b4ea12037ca9d1f291c1519a074079390e0e9849514a637a4fe394845b1c125a

See more details on using hashes here.

File details

Details for the file miller_rabin-1.0.1-cp36-cp36m-manylinux1_x86_64.whl.

File metadata

  • Download URL: miller_rabin-1.0.1-cp36-cp36m-manylinux1_x86_64.whl
  • Upload date:
  • Size: 330.1 kB
  • Tags: CPython 3.6m
  • Uploaded using Trusted Publishing? No
  • Uploaded via: twine/3.1.1 pkginfo/1.5.0.1 requests/2.23.0 setuptools/46.1.3 requests-toolbelt/0.9.1 tqdm/4.44.1 CPython/3.7.7

File hashes

Hashes for miller_rabin-1.0.1-cp36-cp36m-manylinux1_x86_64.whl
Algorithm Hash digest
SHA256 9451ca588f408cc84148d80843130e8cedad17a987246aaa4799e67cc54e0be2
MD5 c19463fc3aab71c148e6d8062fbc7edc
BLAKE2b-256 63faecf48f2bb025dc20adf78383098d0c2201731da407800b567ea37e3b50d8

See more details on using hashes here.

File details

Details for the file miller_rabin-1.0.1-cp36-cp36m-macosx_10_13_x86_64.whl.

File metadata

  • Download URL: miller_rabin-1.0.1-cp36-cp36m-macosx_10_13_x86_64.whl
  • Upload date:
  • Size: 131.6 kB
  • Tags: CPython 3.6m, macOS 10.13+ x86-64
  • Uploaded using Trusted Publishing? No
  • Uploaded via: twine/3.1.1 pkginfo/1.5.0.1 requests/2.23.0 setuptools/46.1.3 requests-toolbelt/0.9.1 tqdm/4.44.1 CPython/3.7.7

File hashes

Hashes for miller_rabin-1.0.1-cp36-cp36m-macosx_10_13_x86_64.whl
Algorithm Hash digest
SHA256 caaac3cba2c91961b85fb3108b5129a26a52932dff687648967cbb534cb14d1a
MD5 2bfa8a44fc7650ec1a95c4d142603c7e
BLAKE2b-256 75170e1a150c9477a170f9516f47ec06ce1f4e7fcded6f045693c58dbf17e1b5

See more details on using hashes here.

Supported by

AWS Cloud computing and Security Sponsor Datadog Monitoring Fastly CDN Google Download Analytics Pingdom Monitoring Sentry Error logging StatusPage Status page