Proth primes are numbers of the form k * 2^n + 1. They have a neat property: Proth's theorem gives you a deterministic proof of primality, not just a probabilistic test. If you can find an integer a where a^((p-1)/2) = -1 mod p, the number is proven prime. No "probably" about it.
The interesting part is the hardware. The core is a 4096-bit Montgomery CIOS multiplier running on a Zynq-7020. It uses 28 DSP48E1 slices and runs at 74 MHz, doing one full modular multiply in ~8,514 clock cycles. The host PC runs an algebraic sieve (eliminates ~92% of candidates using discrete logarithms mod small primes), precomputes the Montgomery constants, then ships each candidate to the FPGA over UART at 115200 baud.
PrimeGrid has exhaustively searched all k < 1200 up to n > 3,000,000. Everything above k = 1200 is wide open. I picked k = 2079 because my sieve showed it had the most surviving candidates at high n. Nobody had ever tested it before.
The prime also divides 5 Generalized Fermat Numbers, which was an unexpected bonus.
12 hardware bugs found along the way. Highlights: Vivado 2019.1 silently prunes register bits when a muxed datapath has sources of different widths. The Montgomery CIOS algorithm produces results in [0, 2p) not [0, p), and without normalizing after every multiply, the error compounds across thousands of squarings. Non-blocking assignments in Verilog mean your "combinational" readout is actually one cycle stale.
All RTL (Verilog), Python scripts, and build files are open source.
Verify it yourself: p = 2079 * (1 << 3718) + 1 print(pow(5, (p-1)//2, p) == p - 1) # True
No comments yet.
