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.

Eratosthenes example

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.