title: How to determine if an incredibly large number is prime?
body: <p>The numbers I'm trying to figure out are in this form (some examples):</p>
  
  <p><code>2 ^ 7 - 1</code>, <code>2 ^ 31 - 1</code>, <code>2 ^ 127 - 1</code>, et cetera.</p>
  
  <p>This is not a homework question I was just researching primes and a lot of the information is going a bit over my head (Fourier transformations). Originally I was just using a function like this:</p>
  
  <pre><code>public static bool IsPrime(int candidate)
  {
      if ((candidate &amp; 1) == 0)
      {
          return candidate == 2;
      }
  
      for (int i = 3; (i * i) &lt;= candidate; i += 2)
      {
          if ((candidate % i) == 0)
          {
              return false;
          }
      }
  
      return candidate != 1;
  }
  </code></pre>
  
  <p>But that stopped working once the numbers got too big. I also looked in to the <a href="http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes" rel="nofollow">Sieve of Eratosthenes</a> but apparently that only works for numbers of much smaller size.</p>
  
  <p>To clarify, I'm not looking to write a program to <em>find</em> prime numbers, but rather, to determine if a given number is prime. I was looking in to the <a href="http://msdn.microsoft.com/en-us/library/system.numerics.biginteger.aspx" rel="nofollow">BigInteger</a> structure in the .NET Framework and it looks promising if I could just write an efficient enough algorithm (I'd settle for something that finished in days).</p>
  
  <p>I'm not sure if a mathematical proof would be better in this circumstance but I do not have much knowledge in that area as opposed to programming but if there was a proof that specialized in these kinds of numbers, that'd definitely be worth looking in to.</p>
  
  <p>Thanks.</p>