kritikov/Fully-Parallel-Prime-Number-Search-on-FPGA
GitHub: kritikov/Fully-Parallel-Prime-Number-Search-on-FPGA
基于循环素数涌现算法的 FPGA 全并行素数搜索硬件架构，以零内存设计实现每步 O(1) 的素数判定。
Stars: 0 | Forks: 0
# FPGA 上的完全并行素数搜索
[](https://doi.org/10.5281/zenodo.20622711)
[](https://opensource.org/licenses/GNU)
[]()
本代码仓库包含 VHDL 硬件设计和测试平台（testbench），用于一种加速素数发现的新型并行硬件架构。通过将 **循环素数涌现算法（Cyclic Prime Emergence Algorithm）** 直接映射到底层硬件结构中，该设计实现了 **每步 $O(1)$ 的素数判定复杂度**。
## 💡 核心理念与突破
传统的软件算法（如埃拉托斯特尼筛法或试除法）在搜索空间增大时，其时间或空间复杂度也会随之增加。
该架构将几何机制转化为数字电路：
* **同心圆 $\rightarrow$ 可编程分频器（Programmable Dividers）：** 每一个被发现的素数 $p$ 都控制着一个独立的、并行的时钟分频器。
* **计圈线（Lap Line） $\rightarrow$ 零溢出检测（Zero-Overflow Detection）：** 当分频器的内部计数器溢出并归零时，它会输出一个脉冲。
* **素数测试 $\rightarrow$ 组合逻辑 OR 门：** 检查候选数 $n$ 是否能被任何已激活的素数整除的操作，被压缩到了一个宽位的组合逻辑归约（Combinatorial Reduction）OR 网络中。
## 📖 详细算法说明
若要深入了解数学概念、几何直觉，以及素数是如何从同步旋转运动中自然涌现的，请阅读作者的完整文章：
🔗 **[当素数从运动中涌现 - nkode.gr](https://nkode.gr/EN/articles/278/when-prime-numbers-emerge-from-motion)**
本文提供了启发本代码仓库中硬件实现的基础理论。
## 📊 核心特性
- **零内存架构（Zero-Memory Architecture）：** 完全消除了 RAM/SRAM 跟踪数组。仅受限于逻辑元件（LUT 和 FF）。
- **完全确定性的时序：** 发现 P 个素数所需的总执行时钟周期数确切为：
$$\text{Cycles} = 11 * (p_P-2) + 2$$
*（其中 $p_P$ 是第 $P$ 个素数的数值）。*
- **高度参数化：** 可通过顶层 generic（`P` 和 `N_BITS`）进行完全配置。
## 📝 引用与研究论文
其数学基础与实现细节已记录在我们发表于 Zenodo 的预印本论文中。
如果您在研究中使用了该架构或算法，请按以下格式进行引用：
Απόσπασμα κώδικα
@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](https://doi.org/10.5281/zenodo.20622711)}
}
⚖️ 许可证
本项目基于 GNU General Public License v3.0（GPLv3 或更高版本）进行许可 - 详情请参阅 LICENSE 文件。
标签：FPGA, VHDL, 并行计算, 硬件开发, 算法硬件加速, 素数计算