nprime 0.0.9

Python library for primes

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

Continuous integration

Travis will be used to run the tests automatically.

Code Quality

Ensured with PEP-8 (for the language format) and Pylint (for the code quality). PyLint is now only run by an other review tool integrated to this repo (codacity, erbert, …)

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"

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

Take a random a ∈ {1,...,n−1} and n > 2, 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.

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