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

Question

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

What would be the best approach for this? I work with C, so 2 ⁿ -1 gets too big to hold when n is large [/ p>

I met the equation (a * b) modp = (a (bmodp)) modp, but I'm not sure if this is applicable in this case, since 2 ⁿ -1 might be simple (or I'm not sure how to change this)

Help evaluate.

Answer 1

You mentioned in the comments that n and p are 9 or 10 digits or something else. If you limit them to 32 bits ( unsigned long ), 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 - it actually does not happen, if p > 2 is simple, but we could also consider the general case - then (2^n - 1) mod p = -1 mod p .

Since the “total remainder” or “remainder” (mod p) is in [0, p - 1] , we add several multiples of p so that it is in this range.

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

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

Answer 2

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

• Do not use (a * b) modp = (a (bmodp)) modp to calculate 2 ⁿ -1 mod p, use it to calculate 2 ⁿ mod p, and then subtract then.
• Fermat's little theorem may be useful here. Thus, the exponent you have to deal with will not exceed p.

Answer 3

To take the module, you somehow need to have 2 ^ n-1, or you are somehow moving in a different direction of the algorithms, an interesting but separate direction, so I recommend that you use the big int concept, as it will be easy .. . make structure and implement large value in small values, for example

  struct bigint{ int lowerbits; int upperbits; } 

decomposition of the expression also has a solution like 2 ^ n = (2 ^ n-4 * 2 ^ 4) -1% p decomposes and processes them separately, which will be pretty algorithmic, then

Answer 4

To calculate 2 ^ n - 1 mod p, you can use exponentiation by squaring after the first removal of any multiple (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 

Answer 5

I came across the answer that I post here when I solve one of the mathematical problems on HackerRank, and it worked for all the test cases given here.

If you limit n and p to 64-bit (without sign lengths) values, then here is a mathematical approach:

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

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

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

If you have any confusion as to whether this relationship is true or not to be added, you can use it for Google 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 attitude to our GP, and you will have your answer !! That is, (2^n - 1)%p equivalent to ( 1 + 2 + 4 + .. + 2^(n-1) )%p and now this relation applies.

Answer 6

Focus on 2 ⁿ mod p first, because you can always subtract it at the end.

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

Consider the operation modulo. If the number is written in the base p, you just grab the last digit. Higher numbers may be discarded.

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

Staying 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 Little Theorem. while ( n -- ) { if ( ret >= limit ) { ret *= 2; ret -= p; } else { ret *= 2; } } return ret; } 

Unfortunately, this still lasts forever for large n and p, and I cannot come up with any theory of higher numbers.

If you have a multiplication tool that can calculate (p-1) ^ 2 without overflow, then you can use a similar algorithm, using repeated squaring with the module after each square operation, and then take the product of a series of squares leftovers, again with the module after each multiplication.

Answer 7

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

step 2.result = boolean and operation x and p