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

Question 1

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;

Question 2

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

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.
Fermat's little theorem can be useful here. That way, the exponent you actually have to deal with won't exceed p.

Question 3

To take modulus you somehow must have 2^n-1 or you will move in a different direction of algorithms, interesting but seperate direction somehow, so i recommend you to use big int concept as it will be easy... make a structure and implement a big value in small values, e.g.

  struct bigint{
    int lowerbits;
    int upperbits;
  }

decomposition of the statement also has solution like 2^n = (2^n-4 * 2^4 )-1%p decompose and seperatly handle them, that will be quite algorithmic then

Question 4

To compute 2^n - 1 mod p, you can use exponentiation by squaring after first removing any multiple of (p - 1) from n (since a^{p-1} = 1 mod p). In pseudo-code:

n = n % (p - 1)
result = 1
pow = 2
while n {
    if n % 2 {
        result = (result * pow) % p
    }
    pow = (pow * pow) % p
    n /= 2
}
result = (result + p - 1) % p

Question 5

I came across the answer that I am posting here, when solving one of the mathematical problems on HackerRank, and it has worked for all the given test cases given there.

If you restrict n and p to 64 bit (unsigned long) values, then here is the mathematical approach :

2^n - 1 can be written as 1*[ (2^n - 1)/(2 - 1) ]

If you look at this carefully, this is the sum of the GP 1 + 2 + 4 + .. + 2^(n-1)

And voila, we know that (a+b)%m = ( (a%m) + (b%m) )%m

If you have a confusion whether the above relation is true or not for addition, you can google for it or you can check this link : http://www.inf.ed.ac.uk/teaching/courses/dmmr/slides/13-14/Ch4.pdf

So, now we can apply the above mentioned relation to our GP, and you would have your answer!! That is, (2^n - 1)%p is equivalent to ( 1 + 2 + 4 + .. + 2^(n-1) )%p and now apply the given relation.

Question 6

First, focus on 2ⁿ mod p because you can always subtract one at the end.

Consider the powers of two. This is a sequence of numbers produced by repeatedly multiplying by two.

Consider the modulo operation. If the number is written in base p, you're just grabbing the last digit. Higher digits can be thrown away.

So at some point(s) in the sequence, you get a two-digit number (a 1 in the p's place), and your task is really just to get rid of the first digit (subtract p) when that happens.

Stopping here conceptually, the brute-force approach would be something like this:

uint64_t exp2modp( uint64_t n, uint64_t p ) {
    uint64_t ret = 1;
    uint64_t limit = p / 2;
    n %= p; // Apply Fermat's Little Theorem.

    while ( n -- ) {
        if ( ret >= limit ) {
            ret *= 2;
            ret -= p;
        } else {
            ret *= 2;
        }
    }
    return ret;
}

Unfortunately, this still takes forever for large n and p, and I can't think of any better number theory offhand.

If you have a multiplication facility which can compute (p-1)^2 without overflow, then you can use an analogous algorithm using repeated squaring with a modulo after each square operation, and then take the product of the series of square residuals, again with a modulo after each multiplication.

Question 7

step 1. x= shifting 1 n times and then subtract 1

step 2.result = logical and operation of x and p