Mersenne Prime search program
marin is an OpenCL™ application.
It determines whether a Mersenne number 2p - 1 is a probable prime using Fermat primality test (a = 3) or prime using Lucas-Lehmer primality test.
It implements an Efficient Modular Exponentiation Proof Scheme. The prp test is validated with Gerbicz - Li error checking.
Efficient multiplication modulo a Mersenne number is evaluated using an Irrational Base Discrete Weighted Transform.
A Number Theoretic Transform is implemented, over the field Z/pZ, p = 264 - 232 + 1 (see: Nick Craig-Wood, IOCCC 2012 Entry).
The algorithm is different from Nick Craig-Wood's implementation:
- By the use of weights, xp - 1 is transformed into xn - 1, where n = 2m or 5 · 2m.
- A recursive polynomial factorization approach splits x2n - r2 into xn - r, xn + r and x5n - r5 into 5 polynomials of the form xn - ri. See: Fast Multiplication.
- Butterfly sizes are radix-4 and radix-5.
algo contains basic implementations of the algorithm. Two main aplications are generated:
- marin_cpu is an implementation of the algorithm on CPU. It is not optimised, it helps to check and debug the OpenCL application.
- marin is the optimised OpenCL application. It can test any prime exponent p in [7; 1,509,949,421].
A checkpoint file is created if the application is interrupted and marin resumes from a checkpoint if it exists.
The compiler must support the built-in __uint128_t type (GCC and Clang) or the _umul128 instruction (Visual Studio).
The code has been validated with GCC 15.2 on Windows (MSYS2) and Linux.