mersenne2

Search for (large) Mersenne primes using (small) Mersenne primes

About

Efficient multiplication modulo a Mersenne number is evaluated using an Irrational Base Discrete Weighted Transform.
A number theoretic weighted transform can be used. Nick Craig-Wood (IOCCC 2012 Entry) implemented it over the field ℤ/pℤ with p = 2⁶⁴ - 2³² + 1.

mersenne2 is an implementation of a (large) Mersenne IBDWT over a set of finite fields GF(M_q²), where M_q is itself a (small) Mersenne prime. A root of unity of order 3 · 2^q+1 exists in GF(M_q²). Hence, the transform length can be any divisor of 3 · 2^q+1.

Let n be the length of the transform. Over the field ℤ/pℤ, if the NTT is a radix-2 transform, the number of operations is K · n · log₂·n. Over the field GF(M_q²), if the NTT is a radix-4 transform of half length then the number of operations is 3/2 · K · n · log₂·n.

M₆₁ = 2⁶¹ - 1 can be compared to 2⁶⁴ - 2³² + 1. The number of modular operations is +50% but the modular reduction is easier to calculate. With GF(M_q²), the weights are powers of two: weighting inputs and unweighting outputs are shift operations.

The important point is that outputs are elements of ℤ/M_qℤ. A residue number system of two or more Mersenne primes can be used and the solution is obtained by the Chinese Remainder Theorem. With M₆₁ and M₃₁, the outputs are 92-bit integers. It is more efficient than the single Mersenne prime M₈₉. GPU are 32-bit processors and an implementation based on (M₆₁; M₃₁) is faster than only M₆₁, if the tested Mersenne number is large enough. The reduction in the size of the transform is a higher gain than the extra 32-bit operations.
The combination of the two Mersenne primes M₆₁ and M₃₁ is now faster than 2⁶⁴ - 2³² + 1.

The Lucas–Lehmer primality test is implemented in C++.
The Mersenne IBDWT is computed over the two fields GF(M₆₁²) and GF(M₃₁²).
The length of the transform is a power of two or three times a power of two.

Build

The compiler must support 128-bit literal values. 64-bit version of GCC and Clang support the built-in __uint128_t type.
The code has been validated using gcc 16 and clang 22.