Primality Tests

A web application to test whether a number is prime using three classical algorithms: Miller–Rabin, Solovay–Strassen, and Baillie–PSW, with real-time benchmarking and comparison.

---

The Problem

Determining whether a large number is prime is a fundamental problem in number theory with direct applications in cryptography (RSA, key generation, etc.). While trial division works for small numbers, it becomes computationally infeasible for large inputs. Probabilistic and hybrid tests offer a practical solution: they run in polynomial time and can decide primality with a controllable, extremely low error probability.

---

Algorithms

Miller–Rabin

A probabilistic test based on Fermat's little theorem and the properties of strong pseudoprimes. It writes n - 1 = 2^k * m and checks, for several random bases a, whether a^m ≡ 1 (mod n) or a specific squaring condition holds. Each round has at most a 1/4 chance of a false positive, so running k = 10 rounds gives an error probability below 4^-10. Fast and widely used in practice.

Solovay–Strassen

One of the first probabilistic primality tests, introduced in 1977. It uses the Jacobi symbol to check whether a^((n-1)/2) ≡ (a/n) (mod n) holds for random bases a. Any composite number fails this test for at least half of all possible bases, giving an error probability of at most 2^-k after k rounds. Slightly less reliable than Miller–Rabin for the same number of rounds.

Baillie–PSW

A hybrid test combining two independent checks: a Miller–Rabin strong probable prime test with base 2, followed by a strong Lucas probable prime test using Selfridge's parameters. The two tests are based on different mathematical foundations, making it extremely unlikely for a composite to pass both. No composite has ever been found that fools Baillie–PSW, making it near-deterministic for all practical inputs.

---

Project Structure

project/
├── static/
│   └── css/
│       └── style.css          # Web interface styles
├── templates/
│   └── index.html             # Main HTML template
├── app.py                     # Flask application
├── Primality_tests.py         # Primality algorithm implementations
└── requirements.txt           # Python dependencies

---

Running the App

1. Create and activate a virtual environment

python -m venv venv

Windows:

venv\Scripts\activate

Linux / Mac:

source venv/bin/activate

2. Install dependencies

pip install -r requirements.txt

3. Start the Flask server

python app.py

4. Open the app in your browser

http://127.0.0.1:5000/

To stop the server, press Ctrl + C in the terminal.

---

Using the Web Interface

1. Enter any integer in the input field
2. Click the button to run the tests
3. The page displays for each algorithm:
   • Result: Prime or Composite
   • Execution time in milliseconds
   • Type: Probabilistic or Hybrid
   • Reliability: Medium / High / Very High
4. A message indicates whether all three algorithms agree on the result (disagreement may suggest a pseudoprime)