Best way to compute ((2^n )-1)mod p

Question

I'm working on a cryptographic exercise, and I'm trying to calculate (2ⁿ-1)mod p where p is a prime number

What would be the best approach to do this? I'm working with C so 2ⁿ-1 becomes too large to hold when n is large

I came across the equation (a*b)modp=(a(bmodp))modp, but I'm not sure this applies in this case, as 2ⁿ-1 may be prime (or I'm not sure how to factorise this)

Help much appreciated.

Answer 1

A couple tips to help you come up with a better way:

1. Don't use (a*b)modp=(a(bmodp))modp to compute 2ⁿ-1 mod p, use it to compute 2ⁿ mod p and then subtract afterward.
2. Fermat's little theorem can be useful here. That way, the exponent you actually have to deal with won't exceed p.

Answer 2

You mention in the comments that n and p are 9 or 10 digits, or something. If you restrict them to 32 bit (unsigned long) values, you can find 2^n mod p with a simple (binary) modular exponentiation:

unsigned long long u = 1, w = 2;

while (n != 0)
{
    if ((n & 0x1) != 0)
        u = (u * w) % p; /* (mul-rdx) */

    if ((n >>= 1) != 0)
        w = (w * w) % p; /* (sqr-rdx) */
}

r = (unsigned long) u;

And, since (2^n - 1) mod p = r - 1 mod p :

r = (r == 0) ? (p - 1) : (r - 1);

---

If 2^n mod p = 0 - which doesn't actually occur if p > 2 is prime - but we might as well consider the general case - then (2^n - 1) mod p = -1 mod p.

Since the 'common residue' or 'remainder' (mod p) is in [0, p - 1], we add a some multiple of p so that it is in this range.

Otherwise, the result of 2^n mod p was in [1, p - 1], and subtracting 1 will be in this range already. It's probably better expressed as:

if (r == 0)
    r = p - 1; /* -1 mod p */
else
    r = r - 1;