## Introduction

I have created a package for prime algorithms called nprime.

Algorithm developed :

- Eratosthenes sieve based
- Fermat’s test (based on Fermat’s theorem)
- Prime generating functions
- Miller Rabin predictive algorithm

To install the package use pip:

```
pip install nprime
```

## Math

Here are a bit of information to help understand some of the algorithms.

### Congruence

The “`≡`

” means congruent, \(a \equiv b \pmod n\) implies that:

For \(\dfrac{kn}{\lparen{a} - {b}\rparen}\) then \(\exists{k} \in \Z\) that verifies \(a = kn + b\)

which implies:

\(a \equiv 0 \pmod n \Leftrightarrow a = kn \Leftrightarrow\) *a* is divisible by *n*

### Strong Pseudoprime

A strong pseudoprime to a base \(a\) is an odd composite number \(n\) with \(n-1 = d\times2^s\) (for \(d\) odd) for some \(r = 0, 1, ..., s-1\) gives either:

\[a^d = 1\pmod n\] \[a^{(d\times2^r)} = -1\pmod n\]### Eratosthenes’ Sieve

#### How to use

Implementation of the sieve of Eratosthenes that discover the primes and their composite up to a limit. It returns a dictionary:

- the key are the primes up to \(n\)
- 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: []}
```

#### Theory

This sieve mark as composite the multiple of each prime. It is an efficient way to find primes. For \(n \in \N\) with \(n > 2\) and for \(\forall a \in[2, ..., \sqrt{n}]\) then \(\frac n a \notin \N\) is true.

### 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 - \frac 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 \(\forall a \in[1, ..., n-1]\)

\[a^{(n-1)} ≡ 1 \pmod n \Leftrightarrow 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 \in \N\) and \(n > 2\), Take a random \(a \in [1,...,n−1]\)

- Find \(d\) and \(s\) such as with \(n - 1 = 2^s \times d\) (with \(d\) odd)
- if \((a^d)^{2^r} \equiv 1 \pmod 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.