Mersenne sayıları, ikinin kuvvetlerinin bir eksiği şeklinde olan sayılardır. n doğal sayısı için Mn = 2n - 1 şeklinde hesaplanır.

Mersenne asal sayıları, hem bir Mersenne sayısı hem de asal olan sayılardır. n sayısı için Mn = 2n - 1 işleminin sonucu bir asal sayı ise bu sayıya Mersenne asal sayısı denir.

Mersenne asal sayılarına örnek olarak,

n = 2 için 22 - 1 = 3
n = 3 için 23 - 1 = 7
n = 5 için 25 - 1 = 31

verilebilir. 3, 7 ve 31 asal sayılardır.

Günümüzde bulunan en büyük asal sayılar, Mersenne asallarından oluşmaktadır. Mersenne asallarının tespit edilmesinde kullanılan bazı pratik yöntemlerden dolayı, yeni asal sayı araştırması yapan gruplar, Mersenne asalları üzerine yoğunlaşmıştır.

2016 'nın Ocak ayı itibariyle 49 Mersenne asal sayısı bilinmektedir. Bilinen en büyük Mersenne asal sayısı 274.207.281 - 1'dir.

Teorem

Bir Mersenne sayısının asal olabilmesi için, ikinin kuvvetinin de asal olması gerekir.

Geometrik seriler için,

s = 1 + r + r2 + r3 + ... + rn-1

Eşitliğin her iki tarafını r ile çarparsak,

rs = r + r2 + r3 + r4 + ... + rn

İki eşitliğin farkı,

s - rs = 1 - rn
s(1 - r) = 1 - rn
rn -1 = s(r - 1)

Teoreme göre, ikinin kuvveti asal değilse, Mersenne sayısının da asal olmaması gerekir. İkinin kuvveti, yani n değeri asal değilse, n değeri axb şeklinde, iki tam sayının çarpımı şeklinde yazılabilir.

2ab değerini 2ab şeklinde yazarsak, 2ab - 1 = s(2a - 1) olur.
2ab değerini 2ba şeklinde yazarsak, 2ba - 1 = s(2b - 1) olur.

Yukarıdaki iki eşitliğe göre, 2^ab - 1 değeri hem 2^a - 1 hem de 2^b - 1 değerine tam olarak bölünür. Yani bu durumda, birden fazla böleni olduğu için 2^ab - 1 değeri asal olmaz.

Lucas-Lehmer Asallık Testi

Bir Mersenne sayısının asal olup olmadığını anlamak için kullanılan etkili bir yöntemdir. Klasik yöntemlere göre, bir Mersenne sayısının asal olup olmadığını tespit etmek için gerekli süre, bu test ile dramatik bir şekilde kısalmaktadır.

Lucas-Lehmer asallık testine göre, 2p - 1 sayısının asal olması için aşağıdaki şartın sağlanması gereklidir.

S(0) = 4
S(n) = (S(n-1)2 - 2) mod (2p-1)

rekürsif fonksiyona göre

S(p-2) = 0

değerini veriyorsa, 2p - 1 Mersenne sayısı asaldır.

Örnek vermek gerekirse, 2⁷ - 1 sayısını asal olup olmadığına bakalım. Bu sayının asal olması için, S(p - 2) yani S(5) değerinin 0 olması gerekir.

S(0) = 4 
S(1) = (4x4 - 2) mod 127 = 14 
S(2) = (14x14 - 2) mod 127 = 67 
S(3) = (67x67 - 2) mod 127 = 42 
S(4) = (42x42 - 2) mod 127 = 111 
S(5) = (111x111 - 2) mod 127 = 0

Dolayısıyla, 2⁷ - 1 sayısı asaldır.

Lucas-Lehmer testinin C# dilinde yazılmış kaynak kodu yer almaktadır.

using System;
using System.Numerics;

namespace SG.Algorithm
{
    public class MersenneNumber
    {
        /// <summary>
        /// (2^p - 1) değerinin asal sayı olup olmadığına bakılıyor.
        /// </summary>
        public bool IsPrimeNumber(int p)
        {
            if (p < 2)
            {
                throw new ArgumentException(nameof(p));
            }

            // Eğer p değeri çift ise, sadece 2 değeri için Mersenne asalı olur.
            if (p % 2 == 0)
            {
                return p == 2;
            }

            // (2^p - 1) sayısının asal olması için, p değerinin de asal olması gerekiyor.
            // Tüm tek sayılara göre mod alma işlemi uygulanarak, p sayısının asal olup olmadığına bakılıyor.
            // Döngünün p^(1/2) ye kadar çalışması yeterli. Hiçbir sayı, karekök değerinden büyük bir sayıya tam olarak bölünemez.
            for (int i = 3; i <= (int)Math.Sqrt(p); i += 2)
            {
                if (p % i == 0)
                {
                    // Tam olarak bölünüyor, asal değil.
                    return false;
                }
            }

            // Değer çok büyük olabileceği için BigInteger kullanılmıştır.
            var mode = BigInteger.Pow(2, p) - 1;

            // S fonksiyonu başlangıç değeri
            var S = new BigInteger(4);

            // S(p-2) değeri bulunacak
            for (int n = 1; n <= p - 2; n++)
            {
                // S(n) = (S(n-1)^2 - 2) mod (2p-1)
                S = (BigInteger.Pow(S, 2) - 2) % mode;
            }

            // S(p-2) değeri 0 ise, (2^p - 1) değeri asaldır.
            return S == 0;
        }
    }
}