Fully Parallel Prime Number Search on FPGA

Based on the Cyclic Prime Emergence Algorithm

This repository contains the VHDL hardware designs and a testbench, for a novel parallel hardware architecture that accelerates prime number discovery. By mapping the Cyclic Prime Emergence Algorithm directly into hardware fabric, this design achieves an $O(1)$ primality evaluation complexity per step.

---

💡 Core Philosophy & Breakthrough

Traditional software algorithms (like the Sieve of Eratosthenes or trial division) scale in time or memory complexity as the search space grows.

This architecture translates geometric mechanics into digital circuits:

• Concentric Circles $\rightarrow$ Programmable Dividers: Every discovered prime $p$ controls an independent, parallel clock divider.
• The Lap Line $\rightarrow$ Zero-Overflow Detection: A divider asserts a pulse when its internal counter overflows back to 0.
• The Primality Test $\rightarrow$ Combinatorial OR Gate: Checking if a candidate $n$ is divisible by any active prime is compressed into a wide combinatorial reduction OR network.

🚀 The $O(1)$ Edge: Regardless of the bit-width of $n$ or the number of synthesized oscillators $P$, the primality test resolves within a single fixed propagation delay of the OR fabric.

---

📖 Detailed Algorithm Explanation

For a deep dive into the mathematical conceptualization, geometric intuition, and how prime numbers naturally emerge from synchronized rotational motion, read the full article by the author:

🔗 When Prime Numbers Emerge from Motion - nkode.gr

This article provides the foundational theory that inspired the hardware implementation found in this repository.

---

📊 Key Features

• Zero-Memory Architecture: Completely eliminates RAM/SRAM tracking arrays. Bounded purely by logic elements (LUTs and FFs).
• Fully Deterministic Timing: Total execution clock cycles to discover P primes is exactly: $$\text{Cycles} = 11 * (p_P-2) + 2$$ (where $p_P$ is the numerical value of the $P$-th prime).
• Highly Parameterized: Fully configurable via top-level generics (P and N_BITS).

---

📝 Citation & Research Paper

The mathematical foundation and implementation specifics are documented in our preprint paper published on Zenodo.

If you use this architecture or algorithm in your research, please cite it as follows: Απόσπασμα κώδικα

@misc{kritikou2026prime, author = {Kritikou, Nikos}, title = {Fully Parallel Prime Number Search on FPGA Based on the Cyclic Prime Emergence Algorithm}, year = {2026}, publisher = {Zenodo}, doi = {10.5281/zenodo.20622711}, url = {https://doi.org/10.5281/zenodo.20622711} }

---

⚖️ License

This project is licensed under the GNU General Public License v3.0 (GPLv3 or later) License - see the LICENSE file for details.