Skip to main content

Python library for primes algorithms

Project description

Generic badge PyPI downloads 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.1 - 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 import sieve_eratosthenes

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

The previous behaviour can be called using the trial_division which uses the Trial Division algorithm

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

Source Distribution

nprime-1.2.1.tar.gz (29.8 kB view hashes)

Uploaded Source

Supported by

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