Skip to main content
Join the official 2019 Python Developers SurveyStart the survey!

Python library for primes algorithms

Project description

Generic badge PyPI version Build Status codecov Codacy Badge

Installation

To install the package use pip:

pip install nprime

Introduction

Some algorithm on prime numbers. You can find all the functions in the file nprime/pryprime.py

Algorithm developed :

  • Eratosthenes sieve based
  • Fermat’s test (based on Fermat’s theorem)
  • Prime generating functions
  • Miller Rabin predictive algorithm

Specifications

  • Language: Python 3.5.2
  • Package:
    • Basic python packages were preferred
    • Matplotlib v2.0 - graph and math

Integration and pipeline

Code quality is monitored through codacity. For the tests coverage, there’s codecov which is run during the Travis CI pipeline.

Math

Here are a bit of information to help understand some of the algorithms

Congruence

” means congruent, a ≡ b (mod m) implies that m / (a-b), ∃ k ∈ Z that verifies a = kn + b

which implies:

a ≡ 0 (mod n) <-> a = kn <-> "a" is divisible by "n"

Strong Pseudoprime

A strong pseudoprime to a base a is an odd composite number n with n-1 = d·2^s (for d odd) for which either a^d = 1(mod n) or a^(d·2^r) = -1(mod n) for some r = 0, 1, ..., s-1

Erathostene’s Sieve

How to use

Implementation of the sieve of erathostenes that discover the primes and their composite up to a limit. It returns a dictionary: - the key are the primes up to n - the value is the list of composites of these primes up to n

from nprime.pyprime import sieve_eratosthenes

# With as a parameter the upper limit
sieve_eratosthenes(10)
>> {2: [4, 6, 8], 3: [6, 9], 5: [], 7: []}

Theory

This sieve mark as composite the multiple of each primes. It is an efficient way to find primes. For n ∈ N with n > 2 and for ∀ a ∈[2, ..., √n] then n/a ∉ N is true.

Erathostene example

Fermat’s Theorem

How to use

A Probabilistic algorithm taking t randoms numbers a and testing the Fermat’s theorem on number n > 1 Prime probability is right is 1 - 1/(2^t) Returns a boolean: True if n passes the tests.

from nprime.pyprime import fermat

# With n the number you want to test
fermat(n)

Theory

If n is prime then ∀ a ∈[1, ..., n-1]

a^(n-1) ≡ 1 (mod n) ⇔ a^(n-1) = kn + 1

Miller rabin

How to use

A probabilistic algorithm which determines whether a given number (n > 1) is prime or not. The miller_rabin tests is repeated t times to get more accurate results. Returns a boolean: True if n passes the tests.

from nprime.pyprime import miller_rabin

# With n the number you want to test
miller_rabin(n)

Theory

For n ∈ N and n > 2, Take a random a ∈ {1,...,n−1} Find d and s such as with n - 1 = 2^s * d (with d odd) if (a^d)^2^r ≡ 1 mod n for all r in 0 to s-1 Then n is prime.

The test output is false of 1/4 of the “a values” possible in n, so the test is repeated t times.

Project details


Download files

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

Files for nprime, version 1.0.0
Filename, size File type Python version Upload date Hashes
Filename, size nprime-1.0.0-py3-none-any.whl (30.3 kB) File type Wheel Python version py3 Upload date Hashes View hashes

Supported by

Elastic Elastic Search Pingdom Pingdom Monitoring Google Google BigQuery Sentry Sentry Error logging AWS AWS Cloud computing DataDog DataDog Monitoring Fastly Fastly CDN SignalFx SignalFx Supporter DigiCert DigiCert EV certificate StatusPage StatusPage Status page