marin

Mersenne Prime search program

About

marin is an OpenCL™ application.
It determines whether a Mersenne number 2^p - 1 is a probable prime using Fermat primality test (a = 3).

It implements an Efficient Modular Exponentiation Proof Scheme. The 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 = 2⁶⁴ - 2³² + 1 (see: Nick Craig-Wood, IOCCC 2012 Entry).

The algorithm is different from Nick Craig-Wood's implementation:

• By the use of weights, x^p - 1 is transformed into xⁿ - 1, where n = 2^m or 5 · 2^m.
• A recursive polynomial factorization approach splits x²ⁿ - r² into xⁿ - r, xⁿ + r and x⁵ⁿ - r⁵ into 5 polynomials of the form xⁿ - r_i. See: Fast Multiplication.
• Butterfly sizes are radix-4 and radix-5.

marin_algo.cpp is a basic implementation 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 [3; 1,509,949,421].

A checkpoint file is created if the application is interrupted and marin resumes from a checkpoint if it exists.

Build

The compiler must support 128-bit literal values. 64-bit versions of GCC and Clang support the built-in __uint128_t type.
The code has been validated with GCC 15.2 on Windows (MSYS2) and Linux.

TODO

• Radix-5 must be be moved from the last stage to the first one.