CODEWITHSUNDEEP
c++modulusmodularreductionexponentiation
user1726493
user1726493

Reputation: 19

Modular exponentiation - how to reduce huge modulus?

the typical equation for modular exponentiation is (a + b) MOD n = ((a MOD n) + (b MOD n)) MOD n. this is awesome if a and b are very huge. however I'm asked to do this exponentiation with a very huge n (2^31 -1) ,a and b are no problem.

I just need a way to reduce n.

Upvotes: 1

Views: 390

Answers (1)

Cheers and hth. - Alf
Cheers and hth. - Alf

Reputation: 145194

"(a + b) MOD n = ((a MOD n) + (b MOD n)) MOD n" isn't exponentation, it's addition.

"(2^31 -1)" isn't a "huge n", it's 31 bits set to 1.

Since these basic assumptions are just plain wrong, and since the question is apparently homework, it's difficult to give any more concrete advice without probably doing the OP a disservice. What's already said should be enough hinting that the assignment can be solved. Or, some start on the assignment can be made, and a new SO question posted.

Upvotes: 2

Related Questions