[Project Share] Modular Projection Sieve: Θ(√N/log N) memory prime sieving with potential for GPU acceleration

Accelerated Computing CUDA CUDA Programming and Performance
1

Hi everyone,

I’m a programmer by training, and I’ve been working on a new prime sieving algorithm that I’d like to share with this community. It’s called the Modular Projection Sieve, and it reduces working memory to Θ(√N / log N).

The core idea is simple: instead of working with numbers N, work with their index k in the representation N = 6k ± 1. Divisibility p | N becomes a modular condition on k, and the problem transforms into avoiding arithmetic progressions. This leads to a memory reduction to just 53 KB to sieve up to 10⁹.

The algorithm has been formally verified in Lean 4 (self-adjointness of the operator, structural isomorphisms) and the code is available in Python/Numba.

I think there might be potential for GPU acceleration, since the algorithm is highly parallelizable at the index level. However, I’m not an expert in CUDA, so I’d love to hear your thoughts or suggestions.

Repository: GitHub - NachoPeinador/modular-projection-sieve: Official repository for the Modular Projection Sieve: a sublinear Θ(√N/log N) memory algorithm based on Kmin± prime-coprime entanglement over (ℤ/6ℤ)ˣ. Features discrete spectral operator analysis (GOE quantum chaos), Lean 4 formal proofs, and reproducible Python/Numba execution up to N=10⁹. · GitHub

DOI: Algebraic Theory of Modular Projection Sieving: Structural Isomorphisms and Spectral Connections in the Distribution of Primes

Any feedback or questions are welcome. Thanks!