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