Python library for primes algorithms

## Project description

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

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

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

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