Skip to main content
Help us improve PyPI by participating in user testing. All experience levels needed!

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.

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

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

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

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

Miller rabin

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


Release history Release notifications

This version
History Node

0.1.8

History Node

0.1.7

History Node

0.1.6

History Node

0.1.5

History Node

0.1.4

History Node

0.1.3

History Node

0.1.2

History Node

0.1.1

History Node

0.1.0

History Node

0.0.9

History Node

0.0.8

History Node

0.0.7

History Node

0.0.6

History Node

0.0.5

History Node

0.0.4

History Node

0.0.3

History Node

0.0.2

History Node

0.0.1

Download files

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

Filename, size & hash SHA256 hash help File type Python version Upload date
nprime-0.1.8.tar.gz (23.2 kB) Copy SHA256 hash SHA256 Source None Mar 13, 2018

Supported by

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