2
\$\begingroup\$

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$

\$\endgroup\$
1
\$\begingroup\$
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 2256, let alone 274207281. 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.

\$\endgroup\$
8
  • \$\begingroup\$ The names I give my functions, class, and namespace are just there for simplicity. I didn't see a whole lot of need to be very specific with them. Though I should probably leave a comment explaining that. Those specified variables are doubles because C# likes any variables involved in math to be of the same data type and Math.Floor returns either decimal or double. Yes, some pieces of code are more of a debugging nature. I will make a note to remove those sorts of things in the future. \$\endgroup\$ – Paradox Oct 18 '16 at 13:07
  • \$\begingroup\$ As for the comment on the return=0, I meant that I was using that statement to ensure that the variable stayed 0 unless it was within the scope of the primes function's for loop. Finally, the "***comment below" comment wasn't so much a reminder as it was a note that the comment below referred to that piece of code. \$\endgroup\$ – Paradox Oct 18 '16 at 13:15
  • \$\begingroup\$ You don't need Math.Floor if you're doing integer division of positive numbers. \$\endgroup\$ – Peter Taylor Oct 18 '16 at 13:30
  • \$\begingroup\$ I think I kinda do because even so, without rounding down, I'm likely to get a non-whole number. I divide the massive exponent into single digit pieces which are easier to handle, round down that number so I'm not doing 2^8.3, and dump the remainder on the variable exp2. I hope I explained that well enough. I could tell from your answer that I didn't explain a whole lot very well. \$\endgroup\$ – Paradox Oct 18 '16 at 23:24
  • \$\begingroup\$ Also, I did look into the Lucas-Lehmer test. It does look fairly simple, but I'm not sure if it's any faster because all it does is square numbers over and over again. Given the massive exponent I'm dealing with, I feel it would kill efficiency. All the same, I will put together a program for it and see if it is any better later on. I appreciate the suggestion. :) \$\endgroup\$ – Paradox Oct 18 '16 at 23:27
2
\$\begingroup\$

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.

\$\endgroup\$
4
  • \$\begingroup\$ Actually, what I'm trying to do there is called modular exponentiation. \$\endgroup\$ – Paradox Oct 17 '16 at 15:11
  • \$\begingroup\$ Link: Khan Academy - Modular exponentiation \$\endgroup\$ – Paradox Oct 17 '16 at 15:15
  • \$\begingroup\$ @Paradox Try what you are doing with smaller numbers and you'll see that what you are doing doesn't work. For example, try with \$2^7\$ and C = 3. \$\endgroup\$ – JS1 Oct 17 '16 at 17:47
  • \$\begingroup\$ Okay, so the absurdly high minimum loop limit is indeed a problem that I'd like to fix. Thank you for making it clearer as to where that would be. I shall be looking into that in order to find a better way of cutting that down more. As for testing out the modular exponentiation with smaller numbers, I will make an edit to the question to draw out that test. \$\endgroup\$ – Paradox Oct 17 '16 at 20:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.