title: MillerRabin primality test in C#
body: <p>Welcome. I am trying to implement MillerRabin test for checking if large given number is a prime. Here is my code:</p>
  
  <pre><code> public static bool MillerRabinTest(BigInteger number)
          {
  
              BigInteger d;
              var n = number - 1;
              var s = FindK(n, out d);
  
              BigInteger a = 2;
              BigInteger y = Calc(a, d, number);  //a^d mod number
              if (y != BigInteger.One &amp;&amp; y != n)
              {
                  for (var r = 1; r &lt;= s - 1; r++)
                  {
                      y = Calc(y, 2, number);
                      if (y == 1)
                          return false;  
                  }
  
                  if (y != n)
                      return false;
              }
              return true; //it is probably prime
          }
  </code></pre>
  
  <p>It is working fine for small Bigintegers. But if my programs needs to evalute numbers containing of more than 16 bits, program freezes. For instance after  succesful  checking if number is a prime, program suddenly is not responsive. I dont understand how is that possible. If it checked one big number, it should have no problem for checking another one again. Even debugger is not being helpful ,becasue  <code>step options</code> disappear. I can share more  code of functions if needed. Above function is working correctly for small numbers.</p>
  
  <p>EDIT. Changing my modulo function for BigInteger.ModPow helped. Unfortunately now for bigger numbers, more than 3000 bits it is never returning prime number which is rather impossible. Or really prme numbers are hard to find out?</p>