Primal-Core: High-Performance Primality Testing Suite

Abstract

Primal-Core is a robust mathematical utility designed for high-speed, cryptographically secure primality evaluation. Developed in Python, the suite implements a hybrid algorithmic approach, leveraging deterministic prime bounds for standard 64-bit integers and the probabilistic Miller-Rabin test for cryptographic-scale numbers.

Mathematical Foundations

Standard trial division approaches operate at a time complexity of $O(\sqrt{n})$, rendering them computationally intractable for large integers. Primal-Core bypasses this limitation by utilizing advanced modular exponentiation, achieving a logarithmic time complexity of $O(k \log^3 n)$, where $k$ is the number of witness iterations.

The Miller-Rabin Algorithm

To evaluate the primality of an odd integer $n > 2$, the algorithm factors $n - 1$ into the form:

$$n - 1 = 2^s \cdot d$$

where $d$ is an odd integer. A chosen base $a$ ($1 < a < n - 1$) acts as a witness for the compositeness of $n$ unless one of the following modular congruence conditions is met:

1. $a^d \equiv 1 \pmod{n}$
2. $a^{2^r \cdot d} \equiv -1 \pmod{n}$ for some integer $r$ in the range $0 \le r < s$

Deterministic Optimization

For processing performance, the suite does not strictly rely on randomness for standard environments. For integers $n < 3,415,500,717,283,211$ (effectively covering 64-bit integer processing), Primal-Core utilizes a specific set of 9 pre-calculated prime bases. This guarantees deterministic, 100% accurate primality evaluation in $O(1)$ witness loops without the risk of pseudoprimes.

System Features

• Hybrid Evaluation Engine: Seamless switching between deterministic execution for standard computational bounds and probabilistic evaluation for large-scale cryptographic keys.
• High-Precision Telemetry: Built-in benchmarking tools measuring execution latency down to fractions of a millisecond utilizing CPU hardware counters (time.perf_counter).
• Interactive CLI: An isolated, interactive shell designed for continuous evaluation and high-load stress testing.

Installation Architecture

It is recommended to deploy Primal-Core within an isolated virtual environment to maintain dependency integrity.

1. Clone the Repository

git clone https://github.com/FN-BuildStack/primal-core.git
cd primal-core

2. Initialize the Virtual Environment

Linux / macOS

python -m venv venv
source venv/bin/activate

Windows PowerShell

python -m venv venv
.\venv\Scripts\Activate.ps1

3. Install Testing Dependencies

pip install -r requirements.txt

Usage and Execution

Initialize the interactive Command Line Interface by executing the source module directly:

python -m src.cli

---

Supported Commands

check <integer>

Performs a direct primality evaluation on the provided integer and returns the modular exponentiation latency.

Example

[primal-core] > check 2147483647
[*] Evaluating: 2147483647...
[+] Result: PRIME
[+] Execution Time: 0.2287 ms

---

benchmark <iterations>

Triggers a high-load stress test, executing the primality suite against massive random integers up to the 64-bit limit:

$$ 2^{64} - 1 $$

Generates a performance matrix upon completion.

Example

[primal-core] > benchmark 50000
[*] Initializing benchmark with 50000 iterations...

---

Test Coverage

The suite includes automated unit tests handled by pytest, verifying:

• Edge cases
• Small primes
• Composite numbers
• Large-scale known primes

Run the test suite with:

pytest tests/