is 2M^2-1 prime?

[Maybeso]

//Number of bits to the right of leading ones bit.
leading_zeros = leadz(n);
nbits = 8*sizeof(n)-leading_zeros;

// Left-justify n and shift leftmost bit off.
n <<= (leading_zeros + 1);

So if I don't have a function leadz(), will this work instead?

if(n == 0) 
    return 1;

while (n>0)  n << 1;
n << 1;

r = a;

// Assumes the loop will not get executed if nbits < 1:
for(i = 1; i < nbits; i++)
{
    r = (r*r)%p;
    // If current (i.e. leftmost) bit = 1, multiply by a:
    if(n < 0)
        r = (a*r)%p;
    // left-shift the exponent:
    n <<= 1;
}
return r;

[Maybeso]

Here is a version of "left-to-right modular binary exponentiation" that has been kicking around the forum for quite a while.

powmod(a, b, m) {

  if (b == 0) return 1;

  mask = 1<<31; // can be adjusted for integer size: 1<<63
  while ((b & mask) == 0) mask >>= 1;
  mask >>= 1;

  r = a;

  while (mask) {
    r = (r * r) % m;
    if (b & mask) {
      r = (r * a) % m;
    }
    mask >>= 1;
  }
  return r;
}