nprime

Installation

Using pip

To install the package use pip:

pip install nprime

Using uv (recommended for development)

uv is a fast Python package manager. To install nprime with uv:

uv add nprime

Contributing

Interested in contributing? See our Contributing Guide for development setup instructions, testing guidelines, and contribution workflows.

Introduction

Some algorithm on prime numbers. You can find all the functions in the file nprime/pryprime.py

Algorithm developed :

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

Specifications

• Language: Python 3.9+ (supports Python 3.9, 3.10, 3.11, 3.12, 3.13)
• Package:
  • Basic python packages were preferred
  • Matplotlib >=3.5.0 - graph and math

Integration and pipeline

For the tests coverage, there's codecov which is run during the GitHub Actions CI pipeline.

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

How to use

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

• 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: []}

The previous behaviour can be called using the trial_division which uses the Trial Division algorithm

Theory

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

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 - 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 ∀ a ∈[1, ..., n-1]

    a^(n-1) ≡ 1 (mod n) ⇔ 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 ∈ 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.