Mersenne Primes Generator in C#

Question

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 <= (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$

Answer 1

namespace Prime
{
    public class Prime
    {

That's not very descriptive. I can tell that Prime.Prime has something to do with primes, but something like NumberTheory.MersennePrimeTester would be a lot more informative.

        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

Why is this a double? Why does its value give "the easiest possible chunks to work with"?

        static int exp = 74207281;

Why is this a static field rather than a local variable?

        static BigInteger big = BigInteger.Pow(2, exp) - 1;

Ditto. Also, why is this never updated?

        static TextWriter tw = new StreamWriter(@"prime.txt"); //writes confirmed primes to a text file

This also doesn't seem like it should be a static field.

        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);

primes is not a descriptive name. It's still unclear why exp is a field. This method would be much better as

public static void Main()
{
    TextWriter tw = new StreamWriter(@"prime.txt");
    // Start at largest known Mersenne prime
    for (int i = 74207281; true; i++)
    {
        if (IsMersenneExponent(i)) tw.WriteLine(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

I asked before why C is double. It seems to me that this could be just

int exp1 = exp / C,
    exp2 = exp % C;

A comment explaining why you split the exponent up base C would be useful.

                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

WTF? That comment is more confusing than explanatory. What is the "this" of "anywhere this appears"? result doesn't even need to exist outside the loop.

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

Was that a reminder to yourself to write a comment explaining what the loop is doing?

                double result1 = (Math.Pow(2, exp1) % i)*C;
                double result2 = (Math.Pow(2, exp2) % i);
                result = (((result1 * result2) - 1) % i);

JS1 has already addressed this in a previous answer: it looks very wrong.

                Console.WriteLine(i);

Why? This looks like debugging code which should have been removed before requesting code review.

A final note. The algorithm appears to be trial division. That's of no practical use for numbers on the order of 2²⁵⁶, let alone 2^74207281. The reason that the majority of the largest known primes are Mersenne is that there's a highly optimised primality test for Mersenne primes. Look into the Lucas-Lehmer test.

Answer 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 <= (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.