To install the package use pip:
pip install nprime
Some algorithm on prime numbers.
Algorithm developed :
- Native one (prime through divisions)
- Eratosthenes sieve based
- Fermat's test (based on Fermat's theorem)
- Prime generating functions
- Miller Rabin predictive algorithm
- Language: Python 3.5.2
- Package:
- Basic python packages were preferred
- Matplotlib v2.0 - graph and math
Travis will be used to run the tests automatically.
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, ...)
Here are a bit of information to help understand some of the algorithms
"≡
" 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"
if n
is prime then ∀ a ∈[1, ..., n-1]
a^(n-1) ≡ 1 (mod n) ⇔ a^(n-1) = kn + 1
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.
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