Mersenne Primes Generator in C# I've made a program in C# that generates Mersenne numbers starting from the current largest known Mersenne prime. It then calculates the modulo between those numbers and smaller ones starting from 3 in order to figure out if it is divisible.

I've used some math tricks to make the process pretty fast, and so I can check the divisibility of what is basically a multi-million digit number against small numbers several times per second. However, I'd like to see if I can make it faster.

Also, if my program does work, it would suggest that the current largest known Mersenne prime (\$2^{74207281} - 1\$) is actually divisible by 7. Therefore I'm hesitant to say that my program actually does work, so if anyone can confirm this for me, I'd also greatly appreciate that!

using System;
using System.IO;
using System.Numerics;

namespace Prime
{
    public class Prime
    {
        const double C = 10601040; //this is a constant that I divide the exponent by to split it into the easiest possible chunks to work with
        static int exp = 74207281;
        static BigInteger big = BigInteger.Pow(2, exp) - 1;
        static TextWriter tw = new StreamWriter(@"prime.txt"); //writes confirmed primes to a text file

        public static void Main()
        {
            for (int i = exp; true; i++) //this loop infinitely runs the prime checker, incrementing the exponent as it goes
            {
                exp++;
                primes(i);
            }
        }

        private static void primes(int exp)
        {
            double div = Math.Floor(exp/C),
                exp1 = div,
                exp2 = exp - (exp1*C), //this is where the exponent is divided into chunks
                result = 0; //anywhere this appears is just to make extra sure that the result stays zero outside the following loop, where the result really matters

            for (long i = 3; i &lt;= (big/i); i+=2)
            {
                double result1 = (Math.Pow(2, exp1) % i)*C;
                double result2 = (Math.Pow(2, exp2) % i);
                result = (((result1 * result2) - 1) % i);
                if (result == 0)
                {
                    Console.WriteLine(exp + ", not prime.");
                    return;
                }
                Console.WriteLine(i);
                result = 0;
            }
            Console.WriteLine(exp);
            tw.WriteLine(exp);
        }
    }
}


I modulo the chunks of the tested number against odd numbers because a Mersenne number will never be even, therefore it's a waste to check for that. Also, I made the stopping point for the loop dynamic so that any extra numbers can be cut out.
It's like this: 377 isn't divisible by 12, so we know that if it is divisible by something, it will be less than \$\frac{377}{12}\$, which is about 31.4. 377's actual factors are 13 and 29 (aside from itself and 1), which are both less than 37.7.

The technique used to modulo these massive numbers is known as modular exponentiation. It works for all numbers. Here's an example.

$2^7, C = 3, I = 5$

$2^7 = 128$

$Mersenne number being tested: 2^7 – 1 = 127 (this is prime)$

$Exp1 = 2$

$Exp2 = 1$

$Result1 = (2^2 % 5) * 3 = (2^2 % 5) * (2^2 % 5) * (2^2 % 5) = 4 * 4 * 4 = 64$

$Result2 = (2^1 % 5) = 2$

$Result = (  (  (64 * 2) – 1) % 5) = (  (  128 – 1) % 5) = (127 % 5) = 2$
Bug

This line seems wrong:


double result1 = (Math.Pow(2, exp1) % i)*C;



It seems like you are implying that:

\$x^y \mod m = ((x \mod m)*y) \mod m\$

But I believe the actual relationship is:

\$x^y \mod m = (x \mod m)^y \mod m\$

This probably explains why your program thinks the known Mersenne prime is divisible by 7.

Loop termination, or lack of it

Your loop is like this:


for (long i = 3; i &lt;= (big/i); i+=2)//***comment below



But big is \$2^{74207281} - 1\$.  Therefore, you intend your loop to run until i reaches \$\sqrt {2^{74207281}-1}\$, meaning i needs to reach about \$2^{37103640}\$.  Unfortunately, your loop index is a long and not a BigInteger, so it can't even represent the numbers you need to represent.  But even if you made i a BigInteger, the loop would run virtually forever because you would need to reach that huge number before you could stop.